/* 
 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 <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);
}
// There is a MAJOR problem with the above program. Run the program
// and try to find out the problem. Fix it!