Cách tạo số nguyên tố (Prime Numbers) trong JavaScript?

Số nguyên tố là số > 1 chỉ chia hết cho 1 và chính nó. Dưới đây là các cách tìm số nguyên tố.

Cách 1: Kiểm tra từng số (O(n√n))

<!DOCTYPE html>
<html>
<body>
    <script>
        function laSoNguyenTo(n) {
            if (n < 2) return false;
            if (n === 2) return true;
            if (n % 2 === 0) return false;
            
            for (let i = 3; i * i <= n; i += 2) {
                if (n % i === 0) return false;
            }
            return true;
        }
        
        // In số nguyên tố từ 1 đến 100
        for (let i = 1; i <= 100; i++) {
            if (laSoNguyenTo(i)) {
                document.write(i + " ");
            }
        }
    </script>
</body>
</html>

Cách 2: Sàng Eratosthenes (Sieve of Eratosthenes) — O(n log log n)

Hiệu quả cho tìm tất cả số nguyên tố ≤ N.

function sieveOfEratosthenes(limit) {
    const isPrime = new Array(limit + 1).fill(true);
    isPrime[0] = isPrime[1] = false;
    
    for (let i = 2; i * i <= limit; i++) {
        if (isPrime[i]) {
            for (let j = i * i; j <= limit; j += i) {
                isPrime[j] = false;
            }
        }
    }
    
    // Trả về mảng số nguyên tố
    return isPrime
        .map((prime, idx) => prime ? idx : -1)
        .filter(x => x !== -1);
}

console.log(sieveOfEratosthenes(100));
// [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]

Cách 3: Generator (lazy evaluation)

function* primeGenerator() {
    yield 2;
    let num = 3;
    const primes = [2];
    
    while (true) {
        const isPrime = primes.every(p => p * p > num || num % p !== 0);
        if (isPrime) {
            primes.push(num);
            yield num;
        }
        num += 2;
    }
}

const gen = primeGenerator();
for (let i = 0; i < 10; i++) {
    console.log(gen.next().value); // 2, 3, 5, 7, 11, 13, 17, 19, 23, 29
}

Tóm tắt độ phức tạp: