[Edit]

JavaScript - finding prime numbers with Sieve of Eratosthenes

1 contributors

2 contributions

0 discussions

7 points

Created by:

Selina-Miranda

737

In this short article, we would like to show how to find prime numbers using Sieve of Eratosthenes and JavaScript.

The main idea of the Sieve of Eratosthenes algorithm is to:

generate array of numbers from 2 to N
(where N is maximal number that we want to check if is prime number),
remove all numbers from the array that are multiplications:
- of 2 giving 4, 6, 8, 10, ..., N
- of 3 giving 6, 9, 12, 15, ..., N
- of 4 giving 8, 12, 16, 20, ..., N
- ...
- up to Math.sqrt(N)
the numbers that were not removed are prime numbers.

Main disadvantage of Sieve of Eratosthenes algorithm is necessary to have big amount of operating memory when we want to find really big numbers.

Main advantage of Sieve of Eratosthenes algorithm is simplicity.

100 first prime numbers (from 0 up to 100):

Edit

	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

Practical example in JavaScript

Edit

In this section removed numbers we mark with false value.

xxxxxxxxxx
 
const findPrimeNumbers = (max) => {
    const places = Array(max);
    places[0] = false;
    places[1] = false;
    for (let i = 2; i < max; ++i) {
        places[i] = true;
    }
    const limit = Math.sqrt(max);
    for (let i = 2; i < limit; ++i) {
        if (places[i]) {
            for (let j = i + i; j < max; j += i) {
                places[j] = false;
            }
        }
    }
    const numbers = new Array();
    for (let i = 2; i < max; ++i) {
        if (places[i]) {
            numbers.push(i);
        }
    }
    return numbers;
};
​
​
// Usage example:
​
console.log(findPrimeNumbers(100)); // from 0 to 100 (excluded)
console.log(findPrimeNumbers(200)); // from 0 to 200 (excluded)

Auto running

Animated prime numbers detection

Edit

In this section we have preseted animation that shows what not prime numbers are removed during next iterations.

xxxxxxxxxx
 
const detectPrimeNumbers = async (max, callback) => {
    const places = Array(max);
    places[0] = false;
    places[1] = false;
    for (let i = 2; i < max; ++i) {
        places[i] = true;
    }
    await callback(null, places, false);
    const limit = Math.sqrt(max);
    for (let i = 2; i < limit; ++i) {
        if (places[i]) {
            for (let j = i + i; j < max; j += i) {
                places[j] = false;
            }
        }
        await callback(i, places, false);
    }
    await callback(null, places, true);
};
​
const sleep = (ms) => new Promise(resolve => setTimeout(resolve, ms));
​
detectPrimeNumbers(100, async (candidate, places, completed) => {
    let text = '';
    if (candidate) {
        text += `removing ${candidate} * n`;
    }
    if (completed) {
        text += 'Prime numbers detected!';
    }
    for (let i = 0; i < places.length; ++i) {
        if (i % 10 === 0) {
            text += '\n|';
        }
        text += ` ${places[i] ? (i < 10 ? ' ' + i : i) : '  '} |`;
    }
    console.clear();
    console.log(text);
    await sleep(1000);
});