//Jeremiah A. Walker
//Prime number generator
//Java
//Sieve of Eratosthenes
/*
The sieve of Eratosthenes is an algorithm we can use for rapidly locating all the prime numbers
within a range of integers. It works by marking all nontrivial multiples of each prime in sequence until
only primes remain unmarked.
It is most well-suited to implementation using arrays, which are compact and feature random access.
*/
import java.util.*; //java.util.Bitset gives a vector of bits that grows as needed.
public class Sieve
{
/*
K is used to indicate the primality of a number 2k + 3. This is done to save time.
BitSet goes into a class to expose some indexer methods.
*/
private BitSet sieve;
public Sieve(int size)
{
sieve = new BitSet((size+1)/2);
}//end Sieve
public boolean is_composite(int k)
{
assert k >= 3 && (k % 2) == 1;
return sieve.get((k-3)/2);
}//end is_composite
public void set_composite(int k)
{
assert k >= 3 && (k % 2) == 1;
sieve.set((k - 3)/2);
}//end set_composite
public static List<Integer> SieveOfEratosthenes(int max)
{
/* The sieve begins by creating the sieve array and then searching for the first zero entry.
All odd multiples of i are set to true to indicate that they are composit. We start with
i-squared because all multiples of i smaller than that are already set to composite.
By default, a BitSet is initialized to all zeroes, as is required by the algorithm
*/
Sieve sieve = new Sieve(max + 1); //+1 to include max itself
for(int i = 3; i*i <= max; i += 2)
{
if(sieve.is_composite(i))
continue;
//we will increment by 2i to skip even multiples of i
for(int multiple_i = i*i; multiple_i <= max; multiple_i += 2*i)
sieve.set_composite(multiple_i);
}//end for
/*When we're done, we iterate through the sieve, forming an ArrayList of elements that are not
composite(IE the numbers that are prime prime) Which returns our prime numbers*/
List<Integer> primes = new ArrayList<Integer>();
primes.add(2);
for(int i = 3; i <= max; i += 2)
if(!sieve.is_composite(i))//if the number is not composite, add to the primes
primes.add(i);
return primes;
}//end Sieve of Eratosthenes
/*Here is the tester. We take a limit value(max), determine the time it took for the computation, and write
a list of our primes. */
public static void main(String[] args)
{
Scanner input = new Scanner(System.in);
System.out.println("Enter a number and I will give you all the primes between zero and that number: ");
int max = input.nextInt();
int num_times = 1;
if (args.length > 0)
max = Integer.parseInt(args[0]);
if(args.length > 1)
num_times = Integer.parseInt(args[1]);
List<Integer> result = null;
long start_time = System.currentTimeMillis();
for(int i = 0; i < num_times; i++)
result = SieveOfEratosthenes(max);
double TimeInMs = (double)(System.currentTimeMillis() - start_time) / num_times;
double time_per_integer_ns = TimeInMs / max * 1000000;
System.out.print("Sieved over integers 1 to " + max + " in " + TimeInMs + "ms (" + time_per_integer_ns + " ns per integer)\n");
for(Integer i : result)
System.out.println(i);
System.out.print("Sieved over integers 1 to " + max + " in " + TimeInMs + "ms (" + time_per_integer_ns + " ns per integer)\n\n");
}//end main
}//end class Sieve