Sejauh manakah Kecekapan Ayak Eratosthenes untuk Penjanaan Nombor Perdana?

Penjanaan Nombor Perdana Paling Elegan: Pendekatan Penapis

Apabila berhadapan dengan cabaran menjana nombor perdana, berusaha untuk keanggunan dalam kod adalah usaha yang mulia. Walaupun banyak kaedah wujud untuk mencari nombor perdana, Ayak Eratosthenes menonjol kerana kesederhanaan dan kecekapannya.

Ayak Eratosthenes beroperasi dengan mencipta tatasusunan boolean panjang n, yang mewakili nombor dari 1 hingga n. Tatasusunan pada mulanya ditetapkan kepada benar untuk semua elemen, menunjukkan bahawa setiap nombor adalah potensi perdana. Algoritma kemudian melelaran melalui tatasusunan, bermula pada nombor pertama yang tidak ditanda, iaitu 2. Ia menandakan semua gandaan 2 sebagai bukan perdana dengan menetapkan nilainya dalam tatasusunan kepada palsu. Ia kemudian beralih ke nombor tidak bertanda seterusnya, 3, dan mengulangi proses, menandakan semua gandaan 3 sebagai bukan perdana. Ini berterusan sehingga nombor terakhir yang tidak ditanda, √(n).

Dengan menggunakan pendekatan ini, Sieve of Eratosthenes mengurangkan dengan ketara bilangan semakan yang diperlukan untuk mencari nombor perdana, menawarkan penyelesaian yang sangat cekap. Pertimbangkan pelaksanaan Java Sieve berikut:

<code class="java">public static BitSet computePrimes(int limit) {
    BitSet primes = new BitSet();
    primes.set(0, false);
    primes.set(1, false);
    primes.set(2, limit, true);
    for (int i = 0; i * i < limit; i++) {
        if (primes.get(i)) {
            for (int j = i * i; j < limit; j += i) {
                primes.clear(j);
            }
        }
    }
    return primes;
}</code>

Kod ini mencipta BitSet untuk mewakili nombor dari 1 hingga n dan menetapkan semua elemen pada mulanya kepada benar. Ia kemudian melelang melalui tatasusunan, menandakan semua gandaan setiap nombor perdana (bermula dengan 2) sebagai bukan perdana. Hasilnya ialah BitSet di mana satu-satunya elemen yang ditetapkan kepada benar mewakili nombor perdana.

Atas ialah kandungan terperinci Sejauh manakah Kecekapan Ayak Eratosthenes untuk Penjanaan Nombor Perdana?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!