[Thuật Toán] Kiếm tra tính chất nguyên tố của một số.

Số nguyên tố là số tự nhiên lớn hơn 1 chia hết cho 1 và chính nó.
* Phương pháp đơn giản nhất để kiểm tra một số n có là số nguyên tố không là kiểm tra xem nó có chia hết cho một số m nằm trong khoảng từ 2 đến n-1 hay không. Nếu n chia hết cho m thì n không là số nguyên tố, ngược lại n là số nguyên tố.
* Ngoài ra do tính chất của Hợp số thì nó chắc chắn có ước số không vượt quá , vì vậy ta chỉ cần kiểm tra từ 2 đến .
* Chúng ta cũng có thể bỏ qua việc kiểm tra các trường hợp là bội số của 2 và 3 bằng cách kiểm tra các số lẻ. Các số lẻ này có dạng 6k-1 và 6k+1 và k = 0, 1, 2, 3...
Chương trình cài đặt.

#include<iostream>
#include<conio.h>
using namespace std;
bool isPrime(int n){
  if(n == 2 || n== 3) return true;
  if(n == 1 || n%2 == 0 || n%3 == 0) return false;
  int k = -1;
  do{
   k+=6;
   if(n%k == 0 || n%(k+2)==0) break;
  }while(k*k < n);// k < sqrt(n);
  return k*k>n;// return k > sqrt(n).
}
int main(){
 int n;
 cout<<"Input number:";
 cin>>n;
 if(isPrime(n)){
  cout<<n<<" is prime";
 }else{
  cout<<n<<" is not prime";
 }
 _getch();
 return 0;
}

Cám ơn bạn đã đọc bài viết này. Hãy chia sẻ bài viết và bình luận ý kiến của bạn ở bên dưới.

Share this

Chào mừng bạn đến với SimpleCodeCJava Blog - Mục đích của chúng tôi khi thành lập blog này là muốn chia sẻ những kiến thức và kinh nghiệm lập trình mà chúng tôi đã học được với mong muốn giúp đỡ mọi người, giúp bạn rút ngắn được thời gian tìm hiểu cũng như việc giải quyết những vấn đề trong lập trình C và Java.