Teacher’s Notes:
=======================================
This is a pretty good assignment for getting students to traverse through an array and apply an operation to each element. It then shows the students how they could do a quick lookup to find if an item is a prime number or not.
Fun Fact - Eratosthenes was the first person to measure the circumference of the Earth and knew that the earth was round in the 3rd century BCE. He calculated this using sticks and shadows.
https://www.youtube.com/watch?v=G8cbIWMv0rI
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 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 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");
}
}
