#include <iostream.h>
#include <stdlib.h>
#include <math.h>
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);
}
Friday, 14 June 2013
Prime number 2 using c++
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment