Prime number problem

Solution: Check If Number Is Prime

function isPrime(n) {
    if (n <= 1) return false;
    if (n <= 3) return true;

    // Eliminate multiples of 2 and 3
    if (n % 2 === 0 || n % 3 === 0) return false;

    // Check for factors of form 6k ± 1 up to √n
    // All primes > 3 are of form 6k ± 1
    for (let i = 5; i * i <= n; i += 6) {
        if (n % i === 0 || n % (i + 2) === 0) {
            return false;
        }
    }

    return true;
}

// Tests
console.log(isPrime(2));    // true
console.log(isPrime(17));   // true
console.log(isPrime(100));  // false
console.log(isPrime(97));   // true

Solution: Sieve of Eratosthenes

function sieveOfEratosthenes(n) {
    if (n < 2) return [];

    // Initialize all as prime
    const isPrime = Array(n + 1).fill(true);
    isPrime[0] = isPrime[1] = false;

    // Sieve
    for (let p = 2; p * p <= n; p++) {
        if (isPrime[p]) {
            // Mark multiples of p as not prime
            // Start from p² (smaller multiples already marked)
            for (let multiple = p * p; multiple <= n; multiple += p) {
                isPrime[multiple] = false;
            }
        }
    }

    // Collect primes
    const primes = [];
    for (let i = 2; i <= n; i++) {
        if (isPrime[i]) {
            primes.push(i);
        }
    }

    return primes;
}

// Test
console.log(sieveOfEratosthenes(30));
// [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

console.log(sieveOfEratosthenes(100).length);  // 25 primes

Space Optimized: Only Odd Numbers

function sieveOptimized(n) {
    if (n < 2) return [];
    if (n === 2) return [2];

    // Only store odd numbers
    const size = Math.floor((n - 1) / 2);
    const isPrime = Array(size + 1).fill(true);

    const primes = [2];  // 2 is the only even prime

    for (let i = 1; i <= size; i++) {
        if (isPrime[i]) {
            const p = 2 * i + 1;  // Convert index to actual number
            primes.push(p);

            // Mark multiples
            if (p * p <= n) {
                for (let j = (p * p - 1) / 2; j <= size; j += p) {
                    isPrime[j] = false;
                }
            }
        }
    }

    return primes;
}

console.log(sieveOptimized(30));
// [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Find Nth Prime

function nthPrime(n) {
    if (n === 1) return 2;

    let count = 1;  // 2 is the first prime
    let candidate = 3;

    while (count < n) {
        if (isPrime(candidate)) {
            count++;
        }
        candidate += 2;  // Only check odd numbers
    }

    return candidate - 2;  // Back up to the nth prime
}

console.log(nthPrime(1));    // 2
console.log(nthPrime(10));   // 29
console.log(nthPrime(100));  // 541

Count Primes Up To N (LeetCode Style)

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

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

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

    // Count trues
    return isPrime.filter(x => x).length;
}

console.log(countPrimes(10));   // 4 (2, 3, 5, 7)
console.log(countPrimes(100));  // 25

Step-by-Step: Sieve Example (n=30)

Initial: [2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30]

p=2: Cross out 4,6,8,10,12,14,16,18,20,22,24,26,28,30
Remaining: [2,3,5,7,9,11,13,15,17,19,21,23,25,27,29]

p=3: Cross out 9,15,21,27 (multiples of 3, starting from 9=3²)
Remaining: [2,3,5,7,11,13,17,19,23,25,29]

p=5: Cross out 25 (5² = 25, only multiple ≤ 30)
Remaining: [2,3,5,7,11,13,17,19,23,29]

p=7: 7² = 49 > 30, stop

Primes: [2,3,5,7,11,13,17,19,23,29]

Complexity Analysis

Method	Time	Space
isPrime (optimized)	O(√n)	O(1)
Sieve	O(n log log n)	O(n)
Sieve optimized	O(n log log n)	O(n/2)
Check each up to n	O(n√n)	O(1)

When To Use What

• Single prime check: Use optimized isPrime, O(√n)
• Many primes up to n: Use Sieve, O(n log log n)
• Large n, limited space: Segmented sieve
• Very large numbers: Miller-Rabin probabilistic test

Common Mistakes

• Not checking √n: Testing up to n is wasteful
• Starting from wrong number: In sieve, start crossing at p², not p
• Including 1 as prime: 1 is not prime by definition
• Missing 2: Only even prime, easy to forget in optimizations

Advanced: Miller-Rabin (For Large Numbers)

// Probabilistic primality test
// Correct for all primes, might incorrectly say composite is prime (rare)
function millerRabin(n, iterations = 5) {
    if (n < 2) return false;
    if (n === 2 || n === 3) return true;
    if (n % 2 === 0) return false;

    // Write n-1 as 2^r * d
    let d = n - 1;
    let r = 0;
    while (d % 2 === 0) {
        d /= 2;
        r++;
    }

    // Test with random witnesses
    for (let i = 0; i < iterations; i++) {
        const a = 2 + Math.floor(Math.random() * (n - 3));
        let x = modPow(a, d, n);

        if (x === 1 || x === n - 1) continue;

        let continueOuter = false;
        for (let j = 0; j < r - 1; j++) {
            x = (x * x) % n;
            if (x === n - 1) {
                continueOuter = true;
                break;
            }
        }

        if (!continueOuter) return false;
    }

    return true;
}

function modPow(base, exp, mod) {
    let result = 1;
    base = base % mod;
    while (exp > 0) {
        if (exp % 2 === 1) {
            result = (result * base) % mod;
        }
        exp = Math.floor(exp / 2);
        base = (base * base) % mod;
    }
    return result;
}

console.log(millerRabin(1000000007));  // true (large prime)

nn

Related Problems

n

n
• ID) . >Check If a Number is Power of Two - Number properties

n

• ID) . >100 Factorial - Large number computation

n

• ID) . >Compute X^Y For Floats and Negative Values - Mathematical algorithms

n