Previous Page

The Sieve of Sundaram- 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 Sundaram 
/								   
/					   					 Descripion:
/		This program uses the Sieve of Sundaram to find all of the prime numbers
/       up to and including the integer	entered by the user.       
/
************************************************************************************/

/***********************************************************************************
				Algorithm:(taken from Wikipedia.com)

  Start with a list of the integers from 1 to n. From this list, remove all
  numbers of the form i + j + 2ij where:

   1)   i,j Elements of N, 1<= i<=j
   2)   i + j + 2ij <= n

 The remaining numbers are doubled and incremented by one, giving a list of the
 odd prime numbers (i.e., all primes except the only even prime 2) below 2n + 2.

 The sieve of Sundaram is equivalent to the sieve of Eratosthenes, except that
 the initial list corresponds only to the odd integers; the work of "crossing out"
 the multiples of 2 is done by the final double-and-increment step.
 Whenever Eratosthenes' method would cross out k different multiples of a prime 2i+1,
 Sundaram's method crosses out i + j(2i+1) for i <= j <= ( arraySize / 2).
************************************************************************************/

import java.util.*;
import javax.swing.JOptionPane;
public class sundaramsSieve
{
    public static void main(String[] args)
    {	
        int[] primes;      
	   String arraySizeStr;
 	   int arraySize;		
		     arraySizeStr=
			JOptionPane.showInputDialog("Enter a number to find all the prime" + 
	  							 " numbers up to that number.");
			arraySize = Integer.parseInt(arraySizeStr);                      
                  primes = SundaramSieve.findPrimes(arraySize);              
        for (int prime : primes)
	   {
           System.out.print(prime + " ");
        }
	      System.out.println();
	      System.out.print("Done!");                   
    }       
	   static public class SundaramSieve 
	   {         
        	public static int[] findPrimes(int arraySize)
	     {//start public static int
            int n = arraySize / 2;
            boolean[] isPrime = new boolean[arraySize];
            Arrays.fill(isPrime, true);
            for (int i = 1; i < n; i++)
		  {
                for (int j = i; j <= (n - i) / (2 * i + 1); j++)
			 {
                    isPrime[i + j + 2 * i * j] = false;
                }
            }				
            int[] primes = new int[arraySize];
            int found = 0;
		  
            if (arraySize > 2) {
                primes[found++] = 2;
            }
            for (int i = 1; i < n; i++)
		  {
                if (isPrime[i])
		      {
                    primes[found++] = i * 2 + 1;
                }
            }				
            return Arrays.copyOf(primes, found);
        }//end of public static int
    }
}

//END OF CODE