Rate this post

Có nhiều cách để kiểm tra số nguyên tố trong C++, một trong số đó là sử dụng vòng lặp để duyệt từ 2 đến căn bậc hai của số cần kiểm tra. Nếu số cần kiểm tra chia hết cho một số trong khoảng này, thì nó không phải là số nguyên tố. Nếu không chia hết cho bất kỳ số nào, thì nó là số nguyên tố.

Các bài viết liên quan;

bool isPrime(int n)
{
    if (n <= 1)
        return false;
    for (int i = 2; i <= sqrt(n); i++)
    {
        if (n % i == 0)
            return false;
    }
    return true;
}

Trong đó, hàm sqrt(n) trả về căn bậc hai của n. Có thể thay thế sqrt(n) bằng n/2, nhưng tùy thuộc vào số lượng số cần kiểm tra, sqrt(n) sẽ là tối ưu hơn, vì nó giảm số lần duyệt vòng lặp.

Thuật toán Sieve of Eratosthenes

Có thể sử dụng thuật toán Sieve of Eratosthenes để tìm các số nguyên tố trong một khoảng nhất định. Thuật toán này sử dụng một mảng bool và tìm tất cả các số nguyên tố trong khoảng từ 2 đến căn bậc hai của số lớn nhất trong khoảng.

void SieveOfEratosthenes(int n)
{
    // Tạo một mảng bool
    bool prime[n+1];
    memset(prime, true, sizeof(prime));

    for (int p=2; p*p<=n; p++)
    {
        // Nếu prime[p] là true thì là số nguyên tố
        if (prime[p] == true)
        {
            // Cập nhật các bội của p
            for (int i=p*p; i<=n; i += p)
                prime[i] = false;
        }
    }

    // In ra các số nguyên tố
    for (int p=2; p<=n; p++)
        if (prime[p])
            cout << p << " ";
}

Thuật toán Miller-Rabin Primality Test

Còn nếu muốn kiểm tra một số cụ thể thì ta có thể sử dụng thuật toán Miller-Rabin Primality Test, nó sử dụng phép chia mũ để kiểm tra số nguyên tố. Thuật toán này sẽ chia một số cần kiểm tra cho một số ngẫu nhiên trong khoảng từ 2 đến căn bậc hai của số cần kiểm tra, nếu chia hết thì sẽ trả về false.

bool isPrime(int n, int k)
{
    // Nếu n là số chẵn hoặc n < 2
    if (n <= 1 || n == 4) return false;
    if (n <= 3) return true;

    // Tìm d và r sao cho n - 1 = 2^r * d
    int d = n - 1;
    int r = 0;
    while (d % 2 == 0) {
        d /= 2;
        r++;
    }

    // Kiểm tra k lần
    while (k--) {
        // Chọn a ngẫu nhiên trong khoảng [2, n-2]
        int a = 2 + rand() % (n - 4);
        int x = pow(a, d) % n;
        int y = 0;

        for (int i = 0; i < r; i++) {
            y = (x * x) % n;
            if (y == 1 && x != 1 && x != n - 1)
                return false;
            x = y;
        }
        if (y != 1)
            return false;
    }
    return true;
}

Cả hai cách trên đều có thể sử dụng để kiểm tra số nguyên tố trong C++. Tuy nhiên, thuật toán Sieve of Eratosthenes thường được sử dụng để tìm tất cả các số nguyên tố trong một khoảng nhất định, trong khi thuật toán Miller-Rabin Primality Test thường được sử dụng để kiểm tra một số cụ thể có phải là số nguyên tố hay không.

Thuật toán trial division

Còn một cách khác là sử dụng thuật toán trial division, đó là tìm tất cả các ước số của số cần kiểm tra, nếu không có ước số nào trừ số 1 và chính nó thì số đó là số nguyên tố.

bool isPrime(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;
}

Tuy nhiên, các thuật toán Miller-Rabin Primality Test và Sieve of Eratosthenes có thể kiểm tra số nguyên tố có độ chính xác cao hơn, còn thuật toán trial division có thể chậm hơn với các số lớn hơn và không thể kiểm tra số nguyên tố trong khoảng lớn. Sự lựa chọn của thuật toán sẽ tùy thuộc vào nhu cầu và mục đích cụ thể của bạn.

C/C++

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

Thuật toán Sieve of Eratosthenes

Thuật toán Miller-Rabin Primality Test

Thuật toán trial division

Trả lời Hủy