エラトステネスの篩

// エラトステネスの篩で素数を列挙する
function sieveOfEratosthenes(limit) {
    if (limit < 2) return [];
    
    // 篩を初期化（全て素数候補として設定）
    const isPrime = Array(limit + 1).fill(true);
    isPrime[0] = isPrime[1] = false; // 0と1は素数ではない
    
    // 篩を実行
    for (let i = 2; i * i <= limit; i++) {
        if (isPrime[i]) {
            // iが素数なら、その倍数を除外
            for (let j = i * i; j <= limit; j += i) {
                isPrime[j] = false;
            }
        }
    }
    
    // 素数を収集
    const primes = [];
    for (let i = 2; i <= limit; i++) {
        if (isPrime[i]) {
            primes.push(i);
        }
    }
    
    return primes;
}

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

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]

// 素数密度の分析
function analyzePrimeDensity(limit) {
    const primes = sieveOfEratosthenes(limit);
    const density = (primes.length / limit) * 100;
    
    return {
        count: primes.length,
        density: density.toFixed(2) + "%",
        largest: primes[primes.length - 1],
        averageGap: primes.length > 1 ? 
            (primes[primes.length - 1] - primes[0]) / (primes.length - 1) : 0
    };
}

console.log(analyzePrimeDensity(100));
// { count: 25, density: "25.00%", largest: 97, averageGap: 3.96 }

console.log(analyzePrimeDensity(1000));
// { count: 168, density: "16.80%", largest: 997, averageGap: 5.95 }

// 最適化版（ビット配列使用）
function optimizedSieve(limit) {
    if (limit < 2) return [];
    
    // ビット配列的なアプローチ（偶数を除外）
    const oddLimit = Math.floor((limit - 1) / 2);
    const isPrime = Array(oddLimit + 1).fill(true);
    
    for (let i = 1; i * (2 * i + 1) <= oddLimit; i++) {
        if (isPrime[i]) {
            const prime = 2 * i + 1;
            for (let j = prime * prime; j <= limit; j += 2 * prime) {
                isPrime[Math.floor((j - 1) / 2)] = false;
            }
        }
    }
    
    const primes = [2]; // 2を追加
    for (let i = 1; i <= oddLimit; i++) {
        if (isPrime[i]) {
            primes.push(2 * i + 1);
        }
    }
    
    return primes;
}

// 区間篩（大きな範囲対応）
function segmentedSieve(low, high) {
    const simplePrimes = sieveOfEratosthenes(Math.sqrt(high));
    const isPrime = Array(high - low + 1).fill(true);
    
    for (const prime of simplePrimes) {
        let start = Math.max(prime * prime, Math.ceil(low / prime) * prime);
        for (let j = start; j <= high; j += prime) {
            isPrime[j - low] = false;
        }
    }
    
    const primes = [];
    for (let i = 0; i < isPrime.length; i++) {
        const num = low + i;
        if (num >= 2 && isPrime[i]) {
            primes.push(num);
        }
    }
    
    return primes;
}

// 大きな範囲の素数を効率的に列挙
console.log(segmentedSieve(1000000, 1000100));
// 1,000,000から1,000,100の範囲の素数

// パフォーマンス比較
function compareMethods(limit) {
    console.time('標準篩');
    const result1 = sieveOfEratosthenes(limit);
    console.timeEnd('標準篩');
    
    console.time('最適化篩');
    const result2 = optimizedSieve(limit);
    console.timeEnd('最適化篩');
    
    console.log(`素数数: ${result1.length} (一致: ${result1.length === result2.length})`);
}

compareMethods(100000); // パフォーマンス比較実行