Apakah Kaedah Paling Elegan untuk Menjana Nombor Perdana N Pertama?

Cara yang elegan untuk menjana nombor perdana

Matlamatnya ialah untuk menulis fungsi generatePrimes(n) yang mengembalikan n nombor perdana yang pertama. Terdapat pelbagai cara untuk mencapai fungsi ini, masing-masing dengan kebaikan dan keburukan mereka sendiri. Artikel ini meneroka kaedah yang paling elegan.

Pendekatan asal biasanya menggunakan gelung bersarang untuk menyemak nombor perdana. Walaupun pendekatan ini berfungsi, ia tidak mempunyai keanggunan kerana strukturnya yang berulang dan bersarang. Pendekatan yang lebih elegan ialah menggunakan Ayak Eratosthenes, yang mempunyai kerumitan masa O(n log log n).

Ayak Eratosthenes berfungsi dengan mencipta tatasusunan boolean saiz n, dengan semua elemen pada mulanya ditetapkan kepada benar. Indeks tatasusunan mewakili nombor dari 0 hingga n-1. Algoritma mula-mula menetapkan elemen pada indeks 0 dan 1 kepada palsu kerana ia bukan nombor perdana. Kemudian, untuk setiap indeks i, ia menetapkan semua gandaan i dalam tatasusunan kepada palsu. Proses ini diulang untuk semua indeks sehingga punca kuasa dua n. Baki elemen benar dalam tatasusunan mewakili nombor perdana.

Berikut ialah pelaksanaan Java yang elegan bagi Sieve of Eratosthenes:

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

Kod ini dengan cekap dan elegan menjana nombor perdana n pertama menggunakan penapis Eratosthenes. Kerumitan masa ialah O(n log log n), kodnya ringkas dan jelas, dan ia sesuai untuk menjana nombor perdana.

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