Số nguyên tố (Prime numbers) là số nguyên lớn hơn 1 và có đúng 2 ước là 1 và chính nó.
Hợp số (Composite numbers) là số nguyên lớn hơn 1 và có nhiều hơn 2 ước.
Ví dụ, 5 là số nguyên tố vì 5 chỉ chia hết cho 1 và 5. Tuy nhiên, 6 là hợp số vì 6 chia hết cho 1, 2, 3 và 6/
Có rất nhiều phương pháp để kiểm tra một số nguyên có phải là số nguyên tố hay không.
- Nếu bạn chỉ kiểm tra một số lượng nhỏ số có phải là số nguyên tố hay không thì chỉ cần kiểm tra xem nó có ước trong khoảng từ 2 đến căn bậc hai của số đó là được.
- Nếu muốn kiểm tra số lượng lớn các số có phải số nguyên tố hay không thì bạn có thể dùng sàn eratosthenes.(Tuy nhiên sẽ tốn một số lượng lớn bộ nhớ) [Code mẫu có trong thư mục FPC]
- Phương án khác bạn có thể dùng câc thuật toán kiểm tra tính nguyên tố theo xác suất, trong số này thì Miller Rabin là thuật toán tương đối dễ hiểu và cài đặt.
Thuật toán "ngây thơ"
bool isPrime(int n) {
for (int i = 2; i < n; i++)
if (n % i == 0) {
// n chia hết cho số khác 1 và chính nó.
return false;
}
return true;
}
Độ phức tạp của thuật toán: O(N) do ta phải duyệt hết các số từ 1 đến N.
Thuật toán tốt hơn
Nếu bạn để ý thì một số nguyên bất kì lớn hơn hoặc bằng 2 thì sẽ luôn có số ước ở nửa đầu căn bậc 2 của nó bằng số ước ở nửa sau căn bậc 2 của nó.
Chú ý: Duyệt tới bé hơn hoặc bằng √N.
bool isPrime(int n) {
for (int i = 2; i <= sqrt(n); i++)
if (n % i == 0) {
return false;
}
return true;
}
Độ phức tạp của thuật toán: O(√N) do ta phải duyệt hết các số từ 1 đến √N.
Sàng Eratosthenes
Sàng Eratosthenes dùng để tìm các số nguyên tố nhỏ hơn hoặc bằng số nguyên N nào đó. Nó còn có thể được sử dụng để kiểm tra một số nguyên nhỏ hơn hoặc bằng N hay không.
Nguyên lí hoạt động của sàng là vào mỗi lần duyệt, ta chọn một số nguyên tố và loại ra khỏi sàng tất cả các bội của số nguyên tố đó mà lớn hơn số đó. Sau khi duyệ xong, các số còn lại trong sàng đều là số nguyên tố.
void sieve(int N) {
bool isPrime[N+1];
for(int i = 0; i <= N;++i) {
isPrime[i] = true;
}
isPrime[0] = false;
isPrime[1] = false;
for(int i = 2; i * i <= N; ++i) {
if(isPrime[i] == true) {
for(int j = i * i; j <= N; j += i)
isPrime[j] = false;
}
}
}
Độ phức tạp của thuật toán: O(N log N)
Thuật toán Miller
Xét số lẻ N > 1, để kiểm tra xem N có phải là số nguyên tố hay không ta làm như sau:
- Phân tích N - 1 thành dạng 2s x d ( s và d là số nguyên dương, d lẻ)
- Xét mỗi số nguyên a = {2, 7, 61}
- Nếu ad ≠ 1 (mod N) và (ad)2^r ≠ -1 (mod n) với mọi r từ 0 đến s - 1 thì N không phải là số nguyên tố
- Nếu N vượt qua được tất cả các lần thử với a ở trên thì N là số nguyên tố
// Hàm phân tích thành dạng 2s X d
void factor(int n) {
s = 0;
while (n % 2 == 0) {
s++;
n = n /2;
}
d = n / s;
}
// Hàm tính ad mod N. Tham khảo tính (a^b) mod c bằng thuật toán chia để trị
int power( int a, int b, int c){
int ans = 1;
for (int i = 1; i <= b; i++){
ans = ans * a;
ans = ans % c;
}
return ans;
}
// Hàm kiểm tra xem Nếu ad ≠ 1 (mod N) và (ad)2^r ≠ -1 (mod n) với mọi r từ 0 đến s - 1 thì N không phải là số nguyên tố . Trả về false nếu không phải số nguyên tố.
bool check( int s, int d, int n, int a) {
if (n == a) return true;
int p = power(a, d, n);
if (p == 1) return true;
while (s--){
if (p == n - 1) return true;
p = p * p % n;
}
return false;
}
// Kiểm tra n với các a khác nhau. True nếu n là số nguyên tố, false nếu n là hợp số.
bool isPrime(int N) {
if (N < 2) return false;
if (N == 2) return true;
int s, d;
factor(N - 1);
return check(s, d, N, 2) && check(s, d, N, 7) && check(s, d, N, 61);
}
Độ phức tạp của thuật toán: O(3 log2N)