C++ প্রোগ্রাম: ফার্মাট মৌলিকতা পরীক্ষা বাস্তবায়ন

ফার্মাট মৌলিকতা পরীক্ষা একটি দত্তক সংখ্যা মৌলিক কিনা তা যাচাই করতে ব্যবহৃত হয়। এখানে এই অ্যালগরিদমের C++ কোড দেওয়া হলো।

অ্যালগরিদম

শুরু
    modulo(base, e, mod)
    a = 1
    b = base
    যতক্ষণ (e > 0)
        যদি (e mod 2 == 1)
            a = (a * b) % mod
        b = (b * b) % mod
        e = e / 2
    a % mod ফেরত দাও
শেষ

শুরু
    Fermat(ll m, int iterations)
    যদি (m == 1)
        false ফেরত দাও
   .done
    for (int i = 0; i < iterations; i++)
        ll x = rand() mod (m - 1) + 1
        যদি (modulo(x, m - 1, m) != 1)
            false ফেরত দাও
        .done
    true ফেরত দাও
শেষ

উদাহরণ কোড

#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 << "মৌলিকতা পরীক্ষার জন্য পূর্ণসংখ্যা দিন: ";
    cin >> num;
    if (Fermat(num, iteration))
        cout << num << " মৌলিক" << endl;
    else
        cout << num << " মৌলিক নয়" << endl;
    return 0;
}

আউটপুট

মৌলিকতা পরীক্ষার জন্য পূর্ণসংখ্যা দিন: 13 মৌলিক