फर्मेट अभाज्यता परीक्षण यह जांचने के लिए किया जाता है कि दी गई संख्या अभाज्य है या नहीं। यहां इस एल्गोरिदम का C++ कोड दिया गया है।
एल्गोरिदम
शुरुआत मोड्यूलो(आधार, घात, मॉड) a = 1 b = आधार जब तक (घात > 0) यदि (घात मॉड 2 == 1) a = (a * b) % मॉड b = (b * b) % मॉड घात = घात / 2 वापस a % मॉड अंत शुरुआत फर्मेट(ll m, इंटरेशन) यदि (m == 1) वापस गलत हो गया लिए (int i = 0; i < इंटरेशन; i++) ll x = रैंड() मॉड (m - 1) + 1 यदि (मोड्यूलो(x, m - 1, m) != 1) वापस गलत हो गया वापस सच अंत
उदाहरण कोड
#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 अभाज्य है
