The Sieve of Eratosthenes 

 

Modules - Data Structures

 

Teacher’s Notes:

========================================================================

This is a good exercise that gets students into working on traversing an array and manipulating the values in it.  

You can also use this assignment to demonstrate how a quick lookup table is used by showing how you can just check for the index of a number instead of doing a sequential search for the number.

In the first FOR loop, we only need to explore factors up to the square root of the largest numbers because any number larger than the square root cannot be a factor of the further numbers in the list.

 

Assignment:

========================================================================

 
The Sieve of Eratosthenes is a mathematical process used to find prime numbers. It works by taking a list of numbers that are sequential from 2 to an upper limit n. It starts by taking the first number in the list (the number 2) and eliminating all of the remaining numbers in the list that are evenly divisible by that number. This would eliminate all of the even numbers. It then takes the next number that has not been eliminated (the number 3) and eliminates any number following it that is evenly divisible. After doing this for all the remaining numbers in the list, the remaining numbers must be prime numbers.  In this program, a number will be eliminated by changing its value to a -1.
 
Write an algorithm that uses the Sieve of Eratosthenes to find all of the prime numbers from 1 to 200,000 and stores them in an array. It then prompts the user to enter a number and then prints out “prime” if the number is a prime number and “not prime” if it is not a prime number.

 

 

Solution (JAVA):

========================================================================

 

 

import java.util.Scanner;
 
public class Sieve {
    public static void main(String[] args) {
        
        int[] number = new int[200000];
        
        //Doing the initial population of values
        for(int x = 0; x < number.length; x++) 
            number[x] = x+1;
        
        //the number 1 is not a prime number so we can eliminate it right away
        number[0] = 0;
        
        //Looking at potential prime numbers
        for(int primeNumberInThisIndex = 1; primeNumberInThisIndex < Math.sqrt(number.length); primeNumberInThisIndex++) {
            if(number[primeNumberInThisIndex] == 0)  //If this number has been already eliminated, move to the next one 
                    continue;
            for(int potentialPrime = primeNumberInThisIndex+1; potentialPrime < number.length; potentialPrime++) {
                //if the number is divisible, eliminate it by turning it into a zero
                if(number[potentialPrime] % number[primeNumberInThisIndex] == 0)
                    number[potentialPrime] = 0;
            }
        }
        
        //Test Code: Display the non-eliminated values in the array
        /*
        for(int x = 0; x < number.length; x++)
            if(number[x] != 0)
                System.out.println(number[x]);
        */
        
        Scanner input = new Scanner(System.in);
        System.out.print("Enter a number to check from 1 to "+ number.length + ": ");
        int value = input.nextInt();
        
        //using the quick-lookup method for checking
        if(number[value-1] != 0)
            System.out.println("prime");
        else
            System.out.println("not prime");
    }
}