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
 * Editor: Notepad++
 * 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 < max; i++)
    		A[i] = true;

		//loop for sieve
    	for(int i = 2; i*i < 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 < 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 >= 2 ; i--)
    	{
    		if(A[i] == true)
    		{
				count++;
				if(count < 49)
    				System.out.print(i + " ");
    		}
    	}
    	return count;
    }

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

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


		System.out.println("\n\nNumber of primes = " + 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("When n = " + n + " it took " + duration / 1000000.0 + " milliseconds");
    }
}

output:

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

Leave a Reply