//  Program: Tabulate the ending digits of prime numbers.
//  Version: 4, uses STL vectors
//  Author:  Chuck Stewart
//  Date:    January, 2001

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

//  Sieve, Version 4: Revised version of the primes counting program
//  that uses STL vectors instead of our templated array.  This
//  includes the important member function push_back which adds primes
//  to the back of the array.  The code assumes the primes array is
//  initially empty.  Notice how much shorter the code is.

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

  // Define and initialize the array of bool.
  vector<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;
  }

  // Fill in the primes vector with the prime integers

  for ( i=2; i<=n; ++i )
    if ( is_prime[i] ) 
      primes.push_back( i );
}


//  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;
  vector<int> primes;
  sieve_of_eratosthenes( n, primes );
  cout << primes.size() << " primes were found.  Here they are.\n";
  for ( int i=0; i<primes.size(); ++i ) {
    cout << primes[i] << " ";
    if ( i!=0 && i%10==0 ) cout << endl;
  }
  cout << 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 vector<int>& primes,
		  vector<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]);
  vector<int> primes;

  //  Apply the sieve and then count the statistics.

  sieve_of_eratosthenes( n, primes );
  vector<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;
}