Thuật Toán về kiếm tra tính chất nguyên tố của một số cài đặt bằng C/C++

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á $\sqrt n$ , vì vậy ta chỉ cần kiểm tra từ 2 đến $\sqrt 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;

}

Chương trình cài đặt

mtoplist