//  Program: Tabulate the ending digits of prime numbers.
//  Version: 1, uses ordinary C and C++ arrays
//  Author:  Chuck Stewart
//  Date:    January, 2001

#include <iostream>
#include <math.h>
#include <stdlib.h>

// Aside: the C++ standard library, which includes stuff that is in
// iostream, is now in a "namespace".  Without the following line we
// would have to prefix cout, cerr and many other objects and
// functions with std:: We avoid this with the following line of code.
// In your future programming efforts, you may need to use namespaces,
// but we will not do so in this course.

using namespace std;


//  Here is the function based on the Sieve of Eratosthenes to find
//  all primes less than or equal to a given number, n.  The function
//  returns the number of primes and a dynamically allocated array
//  containing the primes in increasing order.

void
sieve_of_eratosthenes( int n,
		       int& prime_count,
		       int*& primes)
{
  int i;

  // Allocate space for a bool array that indicates which of the
  // numbers are prime.  Starting at 2, initialize the entries in the
  // array = true.

  bool* is_prime = new bool[n+1];
  for ( i=2; i<=n; ++i )
    is_prime[i] = true;
  
  //  Apply the Sieve of Eratosthenes.  Stop at sqrt(n) because if a
  //  number is composite (not prime), it will have at least one
  //  factor <= sqrt(n).

  for ( i=2; i<=sqrt(n)+1; ++i ) {
    if ( !is_prime[i] ) continue;  // Skip the rest of the loop for non-primes
    int j;
    for ( j=2*i; j<=n; j+=i ) // Mark multiples of prime i to be non-prime
      is_prime[j] = false;
  }

  //  Count the primes 

  prime_count = 0;
  for ( i=2; i<=n; ++i )
    if ( is_prime[i] )
      prime_count ++ ;

  // Allocate space to store the primes and then store them.

  primes = new int[prime_count];
  int k=0;
  for ( i=2; i<=n; ++i )
    if ( is_prime[i] ) {
      primes[k] = i;
      k ++ ;
    }
  
  // Before returning, deallocate the scratch space used for
  // "is_prime".  The [] is used to indicate that an entire array was
  // allocated and therefore an entire array must be deallocated.

  delete [] is_prime;
}


//  A test driver for the Sieve of Eratosthenes function.

void
test_sieve()
{
  int n=200;
  cout << "\nTesting the Sieve for n=" << n << endl;
  int* primes;
  int prime_count=0;
  sieve_of_eratosthenes( n, prime_count, primes );
  cout << prime_count << " primes were found.  Here they are.\n";
  for ( int i=0; i<prime_count; ++i ) {
    cout << primes[i] << " ";
    if ( i!=0 && i%10==0 ) cout << endl;
  }
  cout << endl;
  delete [] primes;
}


//  A function to gather the statistics on the number of primes that
//  end in each digit.

void 
count_remainders( int prime_count,
		  int primes[],
		  int rcount[] )
{
  int i;
  for ( i=0; i<10; ++i )
    rcount[i] = 0;
  for ( i=0; i<prime_count; ++i ) {
    rcount[ primes[i]%10] ++ ;
  }
}


//  Main program for the function that gathers statistics on primes.
//  The main computation is done in the functions
//  sieve_of_eratosthenes and count_remainders.  The first returns an
//  array containing prime numbers and the second gathers the
//  statistics.  These two functions could have been combined into
//  one, but the advantage of the separate sieve_of_eratosthenes
//  function is that it could be used for other purposes.

int 
main( int argc, char* argv[] )
{
  //  test_sieve();
  //  return 0;

  //  n, the upper bound on the primes to consider, is the 1st
  //  argument to the function.

  if ( argc != 2 ) {
    cerr << "Usage: " << argv[0] << " n" << endl;
    return 0;
  }
  int n = int( atof(argv[1]) );
  int nprimes;
  int * prime_numbers;

  //  Apply the sieve and then count the statistics.

  sieve_of_eratosthenes( n, nprimes, prime_numbers );
  int rcount[10];
  count_remainders( nprimes, prime_numbers, rcount );
  
  //  Output the results.
  
  cout << "For primes less than or equal to " << n << ",\n"
       << "here is the counts of the ending digits." << endl;
  for ( int i=0; i<10; ++i )
    cout << i << ": " << rcount[i] << endl;

  delete [] prime_numbers;
  return 0;
}