// primetime.cpp
// Time how much CPU time it takes to find if a number if prime.

#include <iostream>
#include <iomanip>
#include <cmath>
#include <ctime>       //clock(), clock_t and CLOCKS_PER_SEC

using namespace std;

bool is_prime (unsigned long int);


int main () {

  unsigned long int num;

  do {
    cout << "Enter a number to test if it's prime (0 to quit): ";
    cin >> num;
    if (num > 0)
      if (is_prime(num))
        cout << "It's prime" << endl;
      else
        cout << "It's not prime" << endl;
  } while (num > 0);
}




bool is_prime (unsigned long int num) {

  unsigned long int i;
  char ans;

  clock_t start, end;  //clock_t defined in time.h  (a long int)
  start = clock(); //number of "ticks" since program started that CPU has spent
                   //executing this program

  for (i=2; i<=sqrt(num); i++)
    if (num%i == 0)
      break;		// evenly divisible

  end = clock();     
  //convert "ticks" to seconds. IBM PC tick is ~55ms (~1/20 sec)
  //so if takes less than that will report 0.
  //try 1000000007 (prime) the inefficient way to get a non-0 time.
  //  cout << "Time to compute: " << (end - start) / CLK_TCK << endl;
  cout << "Time to compute: " << double(end - start) / CLOCKS_PER_SEC << endl;

  cout << "Compute the inefficient way? (y or n) ";
  cin >> ans;
  if (ans == 'y') {
    start = clock();

    for (i=2; i<=num/2; i++)
      if (num%i == 0)
        break;		// evenly divisible

    end = clock();
    //  cout << "Time to compute: " << (end - start) / CLK_TCK << endl;
    cout << "Time to compute: " <<double(end - start) / CLOCKS_PER_SEC << endl;
  }

  if (i <= sqrt(num))
    return false;
  else
    return true;
}