//  Program: Tabulate the ending digits of prime numbers.
//  Version: 3, uses our templated array class
//  Author:  Chuck Stewart
//  Date:    January, 2001

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

#include "t_array.h"

//  Revised version of the primes counting program that uses the
//  templated array class wherever there is an array.

void
sieve_of_eratosthenes( int n,
		       t_array<int>& primes )
{
  int i;

  // Define and initialize the array of bool.  Look below to see that
  // explicit deletion of the  is_prime array is not needed.

  t_array<bool> is_prime(n+1, 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 ++ ;
    }
}


//  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;
  t_array<int> 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 t_array<int>& primes,
		  t_array<int>& rcount )
{
  int i;
  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 = atoi(argv[1]);
  t_array<int> primes;

  //  Apply the sieve and then count the statistics.

  sieve_of_eratosthenes( n, primes );
  t_array<int> rcount(10,0);
  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;
}