An algorithm to print all the prime numbers up to 100.
We will implement a simple algorithm in javascript to print all the prime numbers from 1 to 100. Everything will be written in ES6.
This problem is also called the Sieve of Eratosthenes.
Sieve of Eratosthenes
It is a very old and simple algorithm to find the all the prime numbers in a given range.
How it works
- We loop all the numbers from 2 up to N.
- In each iteration we mark the current number as
true
and all the other numbers that are divisble by the current number asfalse
. - Then we move to the next number and check if it marked as
true
orfalse
. - If it is
false
then we move to next number and repeat the same steps again. - If it is
true
then we mark all the next numbers divisible by it asfalse
and repeat the same.
Example
Input: 10 Output: [2, 3, 4, 5, 6, 7, 8, 9, 10] [2] = true [4] = false [6] = false [8] = false [10] = false [3] = true [6] = false [9] = false [5] = true [7] = true 2, 3, 5, 7 are the prime numbers from 2 to 10
Implementation
- We will create an array of N + 1 items and mark them as
true
. - Then we will mark the 0th and 1st element as false in the beginning.
- We will then loop from 2 to N and mark all the number divisble by current number as
false
. - We will repeat the same for all the number which will be marked as
true
.
let allPrimes = (n) => { //Create new n+1 array and mark them as true let isPrime = new Array(n+1).fill(true); isPrime[0] = false; isPrime[1] = false; let primes = []; for(let i = 2; i <= n; i++){ //if the number is if(isPrime[i] === true){ primes.push(i); } //mark all the numbers divisible i as false let next = i * i; while (next <= n) { isPrime[next] = false; next += i; } } return primes; }
Input: console.log(allPrimes(100)); Output: [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]
Time complexity: O(n * log(log(n))).
Space complexity: O(n).
Time and Space complexity
- We are finding the all reciprocals of each prime numbers like n(1/2 + 1/3 + 1/5 + 1/7 ... + 1/n) and we are doing it for all the numbers upto n = O(n * log(log(n))). Learn more about it here.
- We are storing all the prime numbers in an array and in the worst case all the numbers can be prime, so Space complexity is O(n).
Emily says:
I don’t think that’s the right time complexity. It should be O(n*log(n)).
Prashant Yadav says:
I have clearly mentioned why the time complexity is O(n * log(log(n))). If you don’t feel so then prove it.