Program to print all the prime numbers from 1 to 100.

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 as false.
• Then we move to the next number and check if it marked as true or false.
• 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 as false 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).