//  Source File Name: SieveBenchmark.java

import java.util.*;
import java.math.*;

// "Sieve of Eratosthenes" benchmark (counts primes <= a given limit).
// The sieve algorithm itself is based on one from _Core Java 2_ by Cay S. Horstmann and
// Gary Cornell. This bitset algorithm is widely used for benchmarking in many languages.
// 'limit' is how far to go looking for primes; 'count' is the number found.
// 'iterations' is the number of complete runs to average before printing results.
// Try iterations > 10 with a moderate count to verify that the standard deviation
// is small. Linearity of performance can be tested by running with various count values.

public class SieveBenchmark {

   private static int count;

   public static void main(String argv[]) {
      if (argv.length == 0 || argv.length > 2) {
         System.out.println("Correct format is");
         System.out.println("java SieveBenchmark <search limit> <iterations to average>");
         System.out.println("<search limit> must be specified, <iterations to average> defaults to 1");
         System.exit(12);
      }
      int limit = Integer.parseInt(argv[0]);
      int iterations = (argv.length == 2) ? Integer.parseInt(argv[1]) : 1;
      long elapsedTimes[] = new long[iterations];

      for(int i = 0; i < iterations; i++) elapsedTimes[i] = runSieve(limit);
      // Round answers and print.
      BigDecimal mean = (new BigDecimal(mean(elapsedTimes))).setScale(2, BigDecimal.ROUND_UP);
      BigDecimal sd = (new BigDecimal(stdDeviation(elapsedTimes))).setScale(2, BigDecimal.ROUND_UP);
      System.out.println("Number of primes <= " + limit + ": " + count);
      System.out.println("Mean execution time: " + mean + " milliseconds");
      System.out.println("Standard deviation: " + sd + " milliseconds");
   }

   // Perform one iteration of the complete sieve; answer the elapsed time.
   private static long runSieve(int limit) {
      long start = System.currentTimeMillis();
      BitSet b = new BitSet(limit);
      count = 0;
      int i;
      for (i = 2; i <= limit; i++) b.set(i);
      i = 2;
      while (i * i <= limit) {
         if (b.get(i)) {
            count++;
            int k = 2 * i;
            while (k <= limit) {
               b.clear(k);
               k += i;
            }
         }
         i++;
      }
      while (i <= limit) {
         if (b.get(i)) count++;
         i++;
      }
      return System.currentTimeMillis() - start;
   }  // End runSieve

   // Compute the arithmetic mean of an array of long integer values.
   private static double mean(long values[]) {
      long sum = 0;
      for(int i = 0; i < values.length; i++) sum += values[i];
      return sum / values.length;
   }

   // Compute the sample standard deviation of an array of long integer values.
   private static double stdDeviation(long values[]) {
      double difference;
      double sumOfSquaredDifferences = 0;
      double mean = mean(values);
      for(int i = 0; i < values.length; i++) {
         difference = mean - values[i];
         sumOfSquaredDifferences += difference * difference;
      }
      return Math.sqrt(sumOfSquaredDifferences / values.length);
   }
} // End class SieveBenchmark