//  Program: Tabulate the ending digits of prime numbers.
//  Version: 2, uses the int_array class
//  Author:  Chuck Stewart
//  Date:    January, 2001

#include <iostream>
#include <math.h>
#include <stdlib.h>
using namespace std;

#include "int_array.h"

//  Revised version of the primes counting program that uses the
//  integer array class to store the primes.  Two important changes
//  are made.  First, the size of the array no longer needs to be
//  passed separately.  Second, the dynamic allocation and
//  deallocation of memory is buried in the construction and
//  destruction of the int_array object.

void
sieve_of_eratosthenes( int n,
		       int_array& 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 

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

  // Tell the primes object how much space is needed to store the
  // primes and then store the primes.

  primes.resize( 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.  Notice no
//  explicit allocation and deallocation of the int_array object is
//  included inside the code.

void
test_sieve()
{
  int n=200;
  cout << "\nTesting the Sieve for n=" << n << endl;
  int_array primes;
  sieve_of_eratosthenes( n, primes );
  cout << primes.size() << " primes were found.  Here they are.\n"
       << primes << endl;
}


//  A function to gather the statistics on the number of primes that
//  end in each digit.  Notice that the primes object is passed by
//  reference, but it is a const.  Passing by reference prevents the
//  expense of calling the copy constructor, while making it a const
//  means only const member functions may be called.  The rcount
//  object is passed by reference because it must be modified.

void 
count_remainders( const int_array& primes,
		  int_array& rcount )
{
  int i;
  for ( i=0; i<10; ++i )
    rcount[i] = 0;
  for ( i=0; i<primes.size(); ++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 fills in an
//  int_array object that contains the prime numbers.  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_array primes;

  //  Apply the sieve and then count the statistics.

  sieve_of_eratosthenes( n, primes );
  int_array rcount(10);
  count_remainders( primes, 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;

  return 0;
}