How to Generate Prime Number Using JavaScript

Prime number is a natural number that has exactly two distinct natural number divisors: 1 and itself. The first 30 prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 and 53.

Prime numbers are very important in computer science. In fact they are used in many algorithms like RSA algorithm which is used for encryption purpose.

The following code is used to print prime numbers using JavaScript:

• Create an array of prime numbers in JavaScript
• Loop through the array and check if each element is a prime number or not
• If it is not then increment counter by one else add its index to array
• Print the count after looping through all elements
  Below is the naïve way of find the prime numbers between 1 and 100

function isPrime(num) {
    for (var i = 2; i < num; i++) {
        if (num % i === 0) {
            return false;
        }
    }
    return num > 1;
}

for (var i = 1; i <= 100; i++) {
    if (isPrime(i)) {
        console.log(i);
    }
}

Lets implement the above algorithm using recursion

function isPrime(num, i = 2) {
    if (num <= 1) {
        return false;
    }
    if (i === num) {
        return true;
    }
    if (num % i === 0) {
        return false;
    }
    return isPrime(num, i + 1);
}

All the above implementations are not efficient the efficient way of implementing the prime algorithm is [Sieve of Eratosthenes] (https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) Below is the implantations of how to generate prime numbers using Sieve of Eratosthenes in JavaScript

function sieveOfEratosthenes(n) {
    var primes = [];
    for (var i = 0; i <= n; i++) {
        primes[i] = true;
    }
    primes[0] = false;
    primes[1] = false;
    for (var i = 2; i <= Math.sqrt(n); i++) {
        for (var j = 2; j * i <= n; j++) {
            primes[i * j] = false;
        }
    }
    var result = [];
    for (var i = 0; i < primes.length; i++) {
        if (primes[i]) result.push(i);
    }
    return result;
}

console.log(sieveOfEratosthenes(100));