Kiểm tra số nguyên tố trong C++

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 nguyên tố là thuật toán được sử dụng để kiểm tra xem số cho trước có phải là số nguyên tố hay không.

Số nguyên tố là số chỉ chia hết cho chính nó. Ví dụ: 2, 3, 5, 7.

Hãy xem một ví dụ để hiểu bài toán của chúng ta:

Đầu vào: 11
Đầu ra: Có

Có nhiều phương pháp để kiểm tra nguyên tố của một số.

Một phương pháp đơn giản để kiểm tra nguyên tố là kiểm tra phép chia của số cho tất cả các số nhỏ hơn N. Nếu bất kỳ số nào chia hết N, thì nó không phải là số nguyên tố.

Kiểm tra cho 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 làm hiệu quả hơn bằng cách thực hiện những thay đổi nhỏ trong thuật toán.

Trước tiên, chúng ta nên kiểm tra các giá trị đến √n thay vì n. Điều này sẽ tiết kiệm nhiều giá trị lặp. √n bao gồm các giá trị của tất cả các ước số có thể của n.

Thay đổi khác có thể là kiểm tra chia cho 2 và 3. Sau đó kiểm tra các giá trị lặp từ 5 đến √n.

Chương trình minh họa 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<<" là số nguyên tố.";
    else
        cout<<n<<" không phải số nguyên tố.";
    return 0;
}

Kết quả

341 không phải số nguyên tố.

Phương pháp hiệu quả hơn khác để kiểm tra nguyên tố của một số là sử dụng phương pháp Fermat dựa trên Định lý Fermat nhỏ.

Định lý Fermat nhỏ Với một số nguyên tố N, mọi giá trị của x thuộc (1, n-1). Điều sau đây đúng:

a ^ (n-1) ≡ 1 (mod n) hoặc a ^ (n-1) % n = 1

Chương trình minh họa triển khai đị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<<" là một số nguyên tố";
    }
    else
        cout<<n<<" không phải là một số nguyên tố";
    return 0;
}

Kết quả

23 là một số nguyên tố