Exercise: Sieve of Eratosthenes
A prime number is a number that is only divisible by 1 and itself. The first prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29.
The sieve of Eratosthenes is an algorithm that finds all prime numbers up to a given limit. The algorithm works as follows:
- Create an array of numbers from 2 to the limit.
- Start with the first number in the array (2). Mark all multiples of 2 as non-prime: 4, 6, 8, 10, 12, etc.
- Move to the next number in the array (3). Mark all multiples of 3 as non-prime: 3, 6, 9, 12, 15, etc.
- Move to the next number in the array (4). Since 4 is already marked as non-prime, skip it.
- Repeat the process until you reach the limit. The numbers that are not marked as non-prime are prime numbers.
To mark a number as non-prime, you can set the value to 0. For example, if the limit is 10, the array of numbers would look like this:
2 3 0 5 0 7 0 0 0
The numbers 2, 3, 5, and 7 are prime numbers. The numbers 4, 6, 8, and 9 and 10 are not prime and thus were replaced with 0.
Your program output should look like this (user input in green):
Enter upper limit (inclusive):
50
Primes from 2 to 50 are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47
Hints 💡
Use methods:
- To create an array containing the values 2, 3, 4, 5, write a method that can be used like this:
int[] nrs = createArray(2, 5);
- To mark the multiples of a number as non-prime, write a method
markMultiplesAsNonPrime that takes an array and a start index as arguments.
More information
Hand in instructions
- Make sure your program runs correctly.
- Hand in your program by uploading Main.java to Moodle.