Problem: Compute all prime numbers less than specified integer
Example:
Input: 100
Output: 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
Algorithm:
We use an algorithm known as the Sieve of Eratosthenes to solve this problem. How it works is that for each prime number starting from 2, we mark all multiples of that number as non prime. At the end of this process, all the prime numbers are identified.
Here’s the detailed steps.
1. Create an array of n items, and mark all values as 1 to mark them as prime.
2. Iterate over the array going from i = 2 to sqrt(n). If i is prime, mark all multiples of i as 0 (non prime)
Java Code:
Advertisement
