#include
#include
#include
int fermatTest (int n)
{
int a;
a = rand() % n;
cout << "Trying with " << a << endl;
return (a == (int(pow(a,n)) % n));
}
int main ()
{
int n, i;
cout << "Enter a natural number: ";
cin >> n;
cout << "How many trials?: ";
cin >> i;
srand(n*i);
while (i > 0)
{
if (fermatTest(n))
{
i = i-1;
}
else
{
cout << "The number " << n << " is definitely not prime." << endl;
return(0);
}
}
cout << "The number " << n << " is probably prime." << endl;
return(0);
}
No comments:
Post a Comment