/*************************************************
How common are primes?

Write a program that reads a number n from the
user and returns the percentage of the first n
integers that are prime (we'll say 1 is *not*
prime).  Write and use a predicate isprime(k)
in your program.  Remember, a number k is prime
if 1 and k are the only numbers that evenly
divide k.
*************************************************/
#include <iostream>
using namespace std;

bool isprime(int);

int main()
{
  // Get value n
  int n;
  cout << "Enter n: ";
  cin >> n;

  // Count number of primes
  int count = 0;
  for(int k = 1; k <= n; k++)
    if (isprime(k))
      count++;

  // Compute and print out percentage
  double p = count/double(n) * 100.0;
  cout << p << "% of the first " << n 
       << " integers are prime!" << endl;

  return 0;
}

/***********************************
 ** isprime(k)
 ***********************************/
bool isprime(int k)
{
  // take care of special case k is 1
  if (k == 1)
    return false;

  // search for divisors in [2,k-1]
  for(int i = 2; i < k; i++)
    if (k % i == 0)
      return false;
  
  // no divisors were found, k's prime!
  return true;
}