Sieve of Eratosthenes
Algorithms and Data Structures
The Sieve of Eratosthenes is an ancient algorithm for discovering primes in a consecutive sequence of natural numbers.
Given a consecutive sequence of natural numbers such as:
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
Starting with 2 (0 and 1 are not prime), eliminate every subsequent second number:
2, 3,4, 5,6, 7, 8, 9,10, 11,12, 13,14, 15,16, 17,18, 19,20
Starting with 3, eliminate every third number:
2, 3,4, 5,6, 7,8,9,10, 11,12, 13,14,15,16, 17,18, 19,20
Repeat the process, each time starting with the next smallest number in the sequence that has not been eliminated. When the limit of the sequence is reached the numbers remaining are the primes:
2, 3, 5, 7, 11, 13, 17, 19
An implementation
// TypeScript
export class SieveOfEratosthenes {
public static findPrimes(upperBound: number = 2): number[] {
const sieve = new Array(upperBound + 1).fill(true);
// 0 and 1 are not prime by definition.
sieve[0] = false;
sieve[1] = false;
for (let i = 2; (i * i) <= upperBound; i++) {
if (sieve[i] === false) {
// The number is not a prime, therefore its multiples will also not be primes.
continue;
}
for (let multiplier = 2; (multiplier * i) <= upperBound; multiplier++) {
// A multiple of a prime is not a prime.
sieve[multiplier * i] = false;
}
}
const primes: number[] = [];
for (let i = 2; i < upperBound; i++) {
if (sieve[i] === true) {
primes.push(i);
}
}
return primes;
}
}
// Test
import { SieveOfEratosthenes } from "../sieve-of-eratosthenes";
describe("SieveOfEratosthenes", () => {
it("is exported", () => {
expect(SieveOfEratosthenes).toBeDefined();
});
describe("findPrimes()", () => {
it("returns all prime numbers in a given bound set", () => {
const knownPrimes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47];
expect(SieveOfEratosthenes.findPrimes(50)).toEqual(knownPrimes);
});
});
});