## Java: primes

The purpose of this program is to display a sieve of eratosthenes in a Java program to see how long it would calculate all primes in the range of 1 to 10^9. Since hardware is a major factor in performance I have included my pc specifications.

prime.java

```/**
* prime.java
*
* Name: Michael Peng
* ID No.: T00055798
* Course: Comp 3050 Algorithm Design and Analysis
* Purpose: Compute all primes between 2 to n(max) and store them into an array
* Language: Java
* Compiler Version: jdk1.7.0_79
* Operating System: Windows 7
* Computer Specifications:
* - CPU: Intel i7-4770 @3.40GHz
* - Memory: 16GB ram
* - GPU: AMD Radeon HD 8570 Graphics
*
*/

public class prime {

//time when program executes
final static long startTime = System.nanoTime();

/*
* Pre: have an integer max in param that is greater then 2
*
* Post: return an array of booleans with associated index's be
*		either true or false depending on whether they are prime
*
* Algorithm: Loop through once to make all values true, then
*			 use a sieve of eratosthenes (link below) to determine if a
*			 number is not prime, make that index false if not prime.
*
* Source: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
*/
public static boolean[] Store_Prime(int max){

boolean[] A = new boolean[max];

//loop for making all values true
for(int i = 2; i &lt; max; i++)
A[i] = true;

//loop for sieve
for(int i = 2; i*i &lt; max - 1; i++)
{
if(A[i] == true)
{
//if there is a number that is a multiple of another number
for(int j = 2; j*i &lt; max; j++)
{
A[j*i] = false;
}
}
}
return A;
}

/*
* Pre: have used the Store_Prime function to calculate all the primes
*	   in a boolean array
*
* Post: return the number of primes that is in the array and
* 		print the primes in reverse order and only the first 50
*
* Algorithm: Loop through the array once and check if
*			 the index is true, if so print and store it in a counter
*
*/
public static int Print_Prime(boolean[] A){

int count = 0;

//loops through array backwards printing first 50 primes
for(int i = A.length-1; i &gt;= 2 ; i--)
{
if(A[i] == true)
{
count++;
if(count &lt; 49)
System.out.print(i + &quot; &quot;);
}
}
return count;
}

//This is the main tester
public static void main(String[] args) {

int n;
n = 1000000000;//n = 10^9

System.out.println(&quot;\n\nNumber of primes = &quot; + Print_Prime(Store_Prime(n)));

//Program end time, to calculate how long it ran subtract start time
final long duration = System.nanoTime() - startTime;
System.out.println(&quot;When n = &quot; + n + &quot; it took &quot; + duration / 1000000.0 + &quot; milliseconds&quot;);
}
}

```

output:

Number of primes = 50847534
When n = 1000000000 it took 21504.819887 milliseconds