Chương trình C++ thực hiện kiểm tra nguyên tố Fermat

Kiểm tra nguyên tố Fermat được dùng để xác định xem một số cho trước có phải là số nguyên tố hay không. Dưới đây là mã C++ thực hiện thuật toán này.

Thuật toán

Bắt đầu
    modulo(cơ_số, mũ, mod)
    a = 1
    b = cơ_số
    while (mũ > 0)
        if (mũ mod 2 == 1)
            a = (a * b) % mod
        b = (b * b) % mod
        mũ = mũ / 2
    trả về a % mod
Kết thúc

Bắt đầu
    Fermat(ll m, int lần_lặp)
    if (m == 1)
        trả về false
    for (int i = 0; i < lần_lặp; i++)
        ll x = rand() mod (m - 1) + 1
        if (modulo(x, m - 1, m) != 1)
            trả về false
    trả về true
Kết thúc

Mã ví dụ

#include <cstring>
#include <iostream>
#include <cstdlib>
#define ll long long
using namespace std;

ll modulo(ll base, ll e, ll mod) {
    ll a = 1;
    ll b = base;
    while (e > 0) {
        if (e % 2 == 1)
            a = (a * b) % mod;
        b = (b * b) % mod;
        e = e / 2;
    }
    return a % mod;
}

bool Fermat(ll m, int iterations) {
    if (m == 1) {
        return false;
    }
    for (int i = 0; i < iterations; i++) {
        ll x = rand() % (m - 1) + 1;
        if (modulo(x, m - 1, m) != 1) {
            return false;
        }
    }
    return true;
}

int main() {
    int iteration = 70;
    ll num;
    cout << "Nhập số nguyên để kiểm tra nguyên tố: ";
    cin >> num;
    if (Fermat(num, iteration))
        cout << num << " là số nguyên tố" << endl;
    else
        cout << num << " không phải là số nguyên tố" << endl;
    return 0;
}

Kết quả đầu ra

Nhập số nguyên để kiểm tra nguyên tố: 13
13 là số nguyên tố