[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;
}