The Sieve of Eratosthenes

 

Modules - CSE2120 Data Structures

 

Teacher’s Notes:

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

Recently, a new record was set for the largest known prime number.  It was announced in October 2024: 

https://www.scientificamerican.com/article/new-prime-number-41-million-digits-long-breaks-math-records/

I joke with the students that if they want to be famous, they just need to find the next prime number after this and they already know where to start searching!

 

Assignment:

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

The Sieve of Eratosthenes

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 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 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.

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 prints a list of all the prime numbers it has found.

 

Solution (JAVA):

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

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        
        int[] number = new int[200000];
        
        for(int x = 0; x < number.length; x++)
            number[x] = x+1;
        
        number[0] = -1;
        
        for(int primeIndex = 1; primeIndex < number.length; primeIndex++)
            for(int x = primeIndex+1; x < number.length; x++) 
                if(number[primeIndex] != -1)
                    if(number[x] % number[primeIndex] == 0)
                        number[x] = -1;
        
        for(int x = 0; x < number.length; x++) {
            if(number[x] != -1)
                System.out.println(number[x]);
            
        }
        
    }
}