#include <iostream.h>
#include <stdlib.h>
#include <math.h>
int fermatTest (int n) {
int a, result, i;
a = rand() % n;
cout << "Trying with " << a << endl;
// return (a == (int(pow(a,n)) % n)); bad way
result = 1;
i = n;
while (i > 0) {
result = (result * a) % n;
i = i-1;
}
return (a == result);
}
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);
}
Friday, 14 June 2013
Prime number 3( Avoid stupid C++ behavior in case of overflow)
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment