Trong bài toán này, chúng ta được cho một số N và nhiệm vụ của chúng ta là kiểm tra xem nó có phải là số nguyên tố hay không.
Kiểm tra tính nguyên bản là thuật toán được sử dụng để kiểm tra xem số đã cho có phải là số nguyên tố hay không.
Số nguyên tố là số chỉ có thể chia cho chính nó. Ví dụ:2, 3, 5, 7.
Hãy lấy một ví dụ để hiểu vấn đề của chúng ta,
Input: 11 Output: Yes
Có nhiều phương pháp để kiểm tra tính chính xác của một số.
Một phương pháp đơn giản để kiểm tra tính nguyên tố là bằng cách kiểm tra phép chia của một số cho tất cả các số nhỏ hơn N. Nếu bất kỳ số nào chia N thì nó không phải là số nguyên tố.
Kiểm tra tất cả i =2 - n-1. Nếu n / i ==0, nó không phải là số nguyên tố.
Phương pháp này có thể được thực hiện hiệu quả hơn bằng cách thực hiện những thay đổi nhỏ này trong thuật toán.
Đầu tiên, chúng ta nên kiểm tra các giá trị cho đến √n thay vì n. Điều này sẽ tiết kiệm rất nhiều giá trị vòng lặp. √n bao gồm các giá trị của tất cả các yếu tố có thể xảy ra của n.
Thay đổi khác có thể là kiểm tra phép chia cho 2 và 3. Sau đó kiểm tra các giá trị vòng lặp từ 5 đến √n.
Chương trình hiển thị việc triển khai thuật toán này
Ví dụ
#include <iostream>
using namespace std;
bool isPrimeNumber(int n){
if (n <= 1)
return false;
if (n <= 3)
return true;
if (n % 2 == 0 || n % 3 == 0)
return false;
for (int i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
return true;
}
int main() {
int n = 341;
if (isPrimeNumber(n))
cout<<n<<" is prime Number.";
else
cout<<n<<" is not prime Number.";
return 0;
} Đầu ra
341 is not prime Number.
Phương pháp khác hiệu quả hơn để kiểm tra tính nguyên thủy của một số là sử dụng phương pháp của Fermat dựa trên Định lý nhỏ của Fermat.
Định lý nhỏ của Fermat Đối với số nguyên tố N, Mọi giá trị của x thuộc (1, n-1). Điều dưới đây là đúng,
a n-1 ≡ 1 (mod n) or a n-1 % n = 1
Chương trình cho thấy việc thực hiện định lý này,
Ví dụ
#include <iostream>
#include <math.h>
using namespace std;
int power(int a, unsigned int n, int p) {
int res = 1;
a = a % p;
while (n > 0){
if (n & 1)
res = (res*a) % p;
n = n/2;
a = (a*a) % p;
}
return res;
}
int gcd(int a, int b) {
if(a < b)
return gcd(b, a);
else if(a%b == 0)
return b;
else return gcd(b, a%b);
}
bool isPrime(unsigned int n, int k) {
if (n <= 1 || n == 4) return false;
if (n <= 3) return true;
while (k>0){
int a = 2 + rand()%(n-4);
if (gcd(n, a) != 1)
return false;
if (power(a, n-1, n) != 1)
return false;
k--;
}
return true;
}
int main() {
int k = 3, n = 23;
if(isPrime(n, k)){
cout<<n<<" is a prime number";
}
else
cout<<n<<" is not a prime number";
return 0;
} Đầu ra
23 is a prime number