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).