Apakah Algoritma Paling Elegan untuk Menjana Nombor Perdana?

Penjanaan Nombor Perdana: Pencarian untuk Keanggunan

Algoritma yang cekap dan menyenangkan dari segi estetika sangat dihargai dalam pengaturcaraan. Artikel ini meneroka kaedah elegan untuk menjana nombor perdana, menambah baik pendekatan awal asas.

Melebihi Asas

Kod asal (tidak ditunjukkan di sini) menawarkan kaedah penjanaan utama yang berfungsi, namun tidak cekap. Beberapa penambahbaikan telah dicadangkan untuk meningkatkan kelajuan dan kebolehbacaan.

Lelaran Dipertingkat

Sumbangan daripada Peter Smit, jmservera dan Rekreativc menyerlahkan pendekatan berulang yang dipertingkatkan. Kaedah ini memperhalusi gelung semakan perdana untuk kecekapan yang lebih tinggi. (Nota: Coretan kod yang disediakan tidak lengkap dan tidak mempunyai logik penting untuk menentukan keutamaan. Contoh yang lengkap dan berfungsi diperlukan untuk perbandingan yang betul.)

Ayak Eratosthenes: Penyelesaian Klasik

Pelaksanaan Sieve of Eratosthenes oleh Starblue menyediakan penyelesaian yang elegan dan cekap. Algoritma ini menandakan gandaan nombor perdana sebagai komposit, dengan ketara mengurangkan overhed pengiraan.

<code class="language-java">public static List<Integer> computePrimes(int limit) {
    boolean[] isPrime = new boolean[limit + 1];
    Arrays.fill(isPrime, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i <= limit; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= limit; j += i) {
                isPrime[j] = false;
            }
        }
    }
    List<Integer> primes = new ArrayList<>();
    for (int i = 2; i <= limit; i++) {
        if (isPrime[i]) {
            primes.add(i);
        }
    }
    return primes;
}</code>

Pendekatan Alternatif

Cadangan lain termasuk memanfaatkan BigInteger dan nextProbablePrime Java untuk ringkas (dfa), menggunakan LINQ untuk penjanaan malas (Maghis) dan pra-menjana dan menyimpan nombor perdana yang besar yang ditetapkan dalam fail untuk akses pantas (darin) .

Kesimpulan

Pendekatan ideal bergantung pada aplikasi khusus dan pilihan pembangun. Sieve of Eratosthenes menawarkan keseimbangan kecekapan dan keanggunan yang kukuh untuk banyak senario. Walau bagaimanapun, kaedah alternatif menyediakan pilihan yang berharga untuk keperluan dan gaya pengekodan yang berbeza.

Atas ialah kandungan terperinci Apakah Algoritma Paling Elegan untuk Menjana Nombor Perdana?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!