द बैली-पीएसडब्ल्यू प्रिमलिटी टेस्ट, इस परीक्षण का नाम रॉबर्ट बैली, कार्ल पोमेरेन्स, जॉन सेल्फ्रिज और सैमुअल वागस्टाफ के नाम पर रखा गया है। यह एक परीक्षण है जो यह परीक्षण करता है कि कोई संख्या एक भाज्य संख्या है या संभवतः अभाज्य है।
एल्गोरिदम
मिलरटेस्ट ()
Begin Declare a function MillerTest of Boolean type. Declare MT_dt and MT_num of integer datatype and pass as the parameter. Declare MT_a and MT_x of integer datatype. Initialize MT_a = 2 + rand( ) % (MT_num - 4). Initialize MT_x = pow(MT_a, MT_dt, MT_num). if (MT_x == 1 || MT_x == MT_num - 1) then return true. while (MT_dt != MT_num - 1) do MT_x = (MT_x * MT_x) % MT_num. MT_dt *= 2. if (MT_x == 1) then return false; if (MT_x == MT_num - 1) then return true. return false. End.
उदाहरण
#include <iostream>
#include<stdlib.h>
using namespace std;
int pow(int pow_a, unsigned int pow_b, int pow_c) {
int result = 1;
pow_a = pow_a % pow_c;
while (pow_b > 0) {
if (pow_b & 1)
result = (result * pow_a) % pow_c;
pow_b = pow_b >> 1;
pow_a = (pow_a * pow_a) % pow_c;
}
return result;
}
bool MiillerTest(int MT_dt, int MT_num) {
int MT_a = 2 + rand( ) % (MT_num - 4);
int MT_x = pow(MT_a, MT_dt, MT_num);
if (MT_x == 1 || MT_x == MT_num - 1)
return true;
while (MT_dt != MT_num - 1) {
MT_x = (MT_x * MT_x) % MT_num;
MT_dt *= 2;
if (MT_x == 1)
return false;
if (MT_x == MT_num - 1)
return true;
}
return false;
}
bool prime(int P_N, int P_K) {
if (P_N <= 1 || P_N == 4)
return false;
if (P_N <= 3)
return true;
int P_D = P_N - 1;
while (P_D % 2 == 0)
P_D /= 2;
for (int i = 0; i < P_K; i++)
if (MiillerTest(P_D, P_N) == false)
return false;
return true;
}
int main() {
int iter = 50;
long num1;
long num2;
cout<< "Enter the first number: ";
cin>>num1;
cout<<endl;
if (prime(num1, iter))
cout<<num1<<" is a prime number\n"<<endl;
else
cout<<num1<<" is a composite number\n"<<endl;
cout<<"Enter another number: ";
cin>>num2;
cout<<endl;
if (prime(num2, iter))
cout<<num2<<" is a prime number\n"<<endl;
else
cout<<num2<<" is a composite number\n"<<endl;
return 0;
} आउटपुट
Enter the first number: 23 23 is a prime number Enter another number: 45 45 is a composite number