Previous Page

The Sieve of Eratosthenes- Java console

Copy and Paste the following code into your favorite Java Integrated Development Environment (IDE) - compile and run.

/ Name: Brian Butler
/ Professor: Gary Hartell
/ Date: April 10, 2011
/ Assignment:Sieve of Eratosthenes 
/					   					 Descripion:
/		This program uses the Sieve of Eratosthenes to find all of the prime numbers
/       up to and including the integer	entered by the user.       

/										   	Algorithm:(taken from
/		1. Create a list of consecutive integers from two to n: (2, 3, 4, ..., n)
/		2. Initially, let p equal 2, the first prime number
/		3. Stating from p, count up by p and cross out thus found numbers in the list
/			(which will be 2p,3p,4p, etc.)
/		4. find the first number not yet crossed out after p; let p now equal this 
/			number ( which is the next prime)
/		5. Repeat steps 3 and 4 until p is greater than n
/		6. All the numbers in the list whhich are not crossed out are prime    

import javax.swing.JOptionPane;
import static java.lang.Math.*;
public class myEratosthenesSieve
	public static void main(String[] args) 
	 String arraySizeStr;
 		int arraySize;
			JOptionPane.showInputDialog("Enter a number to find all the prime" + 
												 " numbers up to that number.");
			arraySize = Integer.parseInt(arraySizeStr);
			int y = (int) sqrt(arraySize);

      boolean[] notPrime = new boolean[arraySize + 1];// Must add 1 to the 
											// array since the array starts out
											// at 0, otherwise the arraySize is not
											// big enough and will give an 
											// ArrayIndexOutOfBoundsException         

      for (int num = 2; num <= y; num++)    //will run through the entire
										    // for loop as long as num is 
											// less than or equal to the 
											// user supplied arraySize.
											// Must start with 2 for it
											// to work, though.         
            if (!notPrime[num]) //if the array's expression (num) is
								//NOT not prime then it will print out
								//the prime number. So these numbers 
								//will be prime and then numbers that
								//are divisible by this number will
								//be put in the notPrime array       
								//Without this if statement, the 
								//program will print every number
								//in the array starting with 2            
                  System.out.print(num + " ");// Prints each Prime Number  
											  //one at a time. The number
											  // two prints right away.   
                  for (int k = num*num ; k <= arraySize; k += num)
						//sets k equal to 2 times 2 initially.
						//So k = 4 and 4 will be discarded into the notPrime 
						//array. k then updates to k + num (which is 4 + 2).
						//So now 6 is discarded..and so on.Until k is greater
						//than the users input for the arraySize.
						//This FOR LOOP gets rid of all of the multiples of
						//the next prime number                   		   
                	 notPrime[k] = true;//numbers not primes go here
					 for (int n = y; n <= arraySize;n++)
					 if (!notPrime[n]) 
                  System.out.print(n + " ");