/* 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!