Count primes

Problem Statement

Solution 1: Using Simple Iteration and Prime Checking

function countPrimesSimple(n) {
    if (n <= 2) return 0;

    function isPrime(num) {
        if (num < 2) return false;
        for (let i = 2; i <= Math.sqrt(num); i++) {
            if (num % i === 0) return false;
        }
        return true;
    }

    let count = 0;
    for (let i = 2; i < n; i++) {
        if (isPrime(i)) count++;
    }
    return count;
} 

const n1 = 10;
countPrimesSimple(n1);  //output: 4 

const n2 = 15;
countPrimesSimple(n2);  //output: 6 

const n3 = 0;
countPrimesSimple(n3);  //output: 0 

Solution 2: Using Sieve of Eratosthenes

function countPrimesSieve(n) {
    if (n <= 2) return 0;

    let isPrime = new Array(n).fill(true);
    isPrime[0] = isPrime[1] = false; // 0 and 1 are not prime

    for (let i = 2; i * i < n; i++) {
        if (isPrime[i]) {
            for (let j = i * i; j < n; j += i) {
                isPrime[j] = false;
            }
        }
    }

    return isPrime.reduce((count, prime) => count + (prime ? 1 : 0), 0);
} 

const n1 = 10;
countPrimesSieve(n1);  //output: 4 

const n2 = 15;
countPrimesSieve(n2);  //output: 6 

const n3 = 0;
countPrimesSieve(n3);  //output: 0 

Solution 3: Using a Set to Track Prime Numbers

function countPrimesSet(n) {
    if (n <= 2) return 0;

    let isPrime = new Array(n).fill(true);
    isPrime[0] = isPrime[1] = false;

    for (let i = 2; i * i < n; i++) {
        if (isPrime[i]) {
            for (let j = i * i; j < n; j += i) {
                isPrime[j] = false;
            }
        }
    }

    return Array.from(new Set(isPrime.map((val, idx) => val ? idx : null).filter(v => v !== null))).length;
} 

const n1 = 10;
countPrimesSet(n1);  //output: 4 

const n2 = 15;
countPrimesSet(n2);  //output: 6 

const n3 = 0;
countPrimesSet(n3);  //output: 0 

Solution 4: Using Dynamic Programming

function countPrimesDynamic(n) {
    if (n <= 2) return 0;

    let isPrime = new Array(n).fill(true);
    isPrime[0] = isPrime[1] = false;

    for (let i = 2; i < n; i++) {
        if (isPrime[i]) {
            for (let j = i * i; j < n; j += i) {
                isPrime[j] = false;
            }
        }
    }

    return isPrime.filter(val => val).length;
} 

const n1 = 10;
countPrimesDynamic(n1);  //output: 4 

const n2 = 15;
countPrimesDynamic(n2);  //output: 6 

const n3 = 0;
countPrimesDynamic(n3);  //output: 0 

Solution 5: Using Array filter Method

function countPrimesFilter(n) {
    if (n <= 2) return 0;

    let isPrime = new Array(n).fill(true);
    isPrime[0] = isPrime[1] = false;

    for (let i = 2; i * i < n; i++) {
        if (isPrime[i]) {
            for (let j = i * i; j < n; j += i) {
                isPrime[j] = false;
            }
        }
    }

    return isPrime.map((val, idx) => val ? idx : null).filter(v => v !== null).length;
} 

const n1 = 10;
countPrimesFilter(n1);  //output: 4 

const n2 = 15;
countPrimesFilter(n2);  //output: 6 

const n3 = 0;
countPrimesFilter(n3);  //output: 0 

Solution 6: Using Map to Track Prime Status

function countPrimesMap(n) {
    if (n <= 2) return 0;

    let isPrime = new Map();
    for (let i = 2; i < n; i++) {
        isPrime.set(i, true);
    }

    for (let i = 2; i * i < n; i++) {
        if (isPrime.get(i)) {
            for (let j = i * i; j < n; j += i) {
                isPrime.set(j, false);
            }
        }
    }

    return Array.from(isPrime.values()).filter(val => val).length;
} 

const n1 = 10;
countPrimesMap(n1);  //output: 4 

const n2 = 15;
countPrimesMap(n2);  //output: 6 

const n3 = 0;
countPrimesMap(n3);  //output: 0 

Solution 7: Using Generators

function* primesGenerator(n) {
    let isPrime = new Array(n).fill(true);
    isPrime[0] = isPrime[1] = false;

    for (let i = 2; i * i < n; i++) {
        if (isPrime[i]) {
            for (let j = i * i; j < n; j += i) {
                isPrime[j] = false;
            }
        }
    }

    for (let i = 2; i < n; i++) {
        if (isPrime[i]) yield i;
    }
}

function countPrimesGenerator(n) {
    return Array.from(primesGenerator(n)).length;
} 

const n1 = 10;
countPrimesGenerator(n1);  //output: 4 

const n2 = 15;
countPrimesGenerator(n2);  //output: 6 

const n3 = 0;
countPrimesGenerator(n3);  //output: 0 

Solution 8: Using Functional Programming

function countPrimesFunctional(n) {
    if (n <= 2) return 0;

    let isPrime = new Array(n).fill(true);
    isPrime[0] = isPrime[1] = false;

    for (let i = 2; i * i < n; i++) {
        if (isPrime[i]) {
            for (let j = i * i; j < n; j += i) {
                isPrime[j] = false;
            }
        }
    }

    return isPrime.reduce((acc, val) => acc + (val ? 1 : 0), 0);
} 

const n1 = 10;
countPrimesFunctional(n1);  //output: 4 

const n2 = 15;
countPrimesFunctional(n2);  //output: 6 

const n3 = 0;
countPrimesFunctional(n3);  //output: 0 

Solution 9: Using While Loop

function countPrimesWhile(n) {
    if (n <= 2) return 0;

    let isPrime = new Array(n).fill(true);
    isPrime[0] = isPrime[1] = false;

    let i = 2;
    while (i * i < n) {
        if (isPrime[i]) {
            let j = i * i;
            while (j < n) {
                isPrime[j] = false;
                j += i;
            }
        }
        i++;
    }

    return isPrime.reduce((count, prime) => count + (prime ? 1 : 0), 0);
} 

const n1 = 10;
countPrimesWhile(n1);  //output: 4 

const n2 = 15;
countPrimesWhile(n2);  //output: 6 

const n3 = 0;
countPrimesWhile(n3);  //output: 0 

Solution 10: Using Nested Loops

function countPrimesNestedLoops(n) {
    if (n <= 2) return 0;

    let count = 0;
    for (let i = 2; i < n; i++) {
        let prime = true;
        for (let j = 2; j * j <= i; j++) {
            if (i % j === 0) {
                prime = false;
                break;
            }
        }
        if (prime) count++;
    }
    return count;
} 

const n1 = 10;
countPrimesNestedLoops(n1);  //output: 4 

const n2 = 15;
countPrimesNestedLoops(n2);  //output: 6 

const n3 = 0;
countPrimesNestedLoops(n3);  //output: 0 

More Problems Solutions