/*
In prime.C it is enough to go to sqrt(n).
Proof: if d is a divisor of n, then so is n/d, but d and n/d cannot
both be greater than sqrt(n). So Prime.C takes O(sqrt(n)) steps.
Here is a better way to test for prime numbers that takes O(log(n)) steps.
The new algortihm uses Fermat's little theorem:
If n is a prime number and a is any positive integer less than n,
then a raised to the nth power is congruent to a modulo n.
In symbols: if n is prime and a < n, then pow(a,n) % n = a
If n is not a prime, then, in general, most of the numbers a < n will not
satisfy the above relation. This leads to the following algorithm.
Given a number n, pick a random number a < n and compute pow(a,n) %
n. If the result is not equal to a, then n is certainly not
prime. If it is a, then chances are good that n is prime. Now pick
another random number and do the same test. If it also satisfies the
equation then we are even more confident that n is prime. This is
called the Fermat test.
Note: The Fermat test is not fool proof. Here are non primes that pass
the Fermat test: 561, 1105, 1729, 2465, 2821, 6601.
*/
#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);
}
// There is a MAJOR problem with the above program. Run the program
// and try to find out the problem. Fix it!