Bagaimanakah Kita Boleh Menjana Nombor Perdana dengan Cekap?

Jana Nombor Perdana dengan Keanggunan dan Kecekapan

Dalam bidang pengaturcaraan, mencari cara yang elegan dan cekap untuk menjana nombor perdana adalah perkara klasik cabaran. Mari kita terokai pendekatan yang menyeimbangkan antara keringkasan dan prestasi.

Pertimbangkan untuk menggunakan teorem nombor perdana, yang menganggarkan bilangan prima kurang daripada atau sama dengan n sebagai pi(n) ≈ n / log(n) . Anggaran ini memberikan batas atas pada saiz ayak yang boleh digunakan untuk mengenal pasti nombor perdana.

Kaedah ayak, juga dikenali sebagai Ayak Eratosthenes, berulang melalui julat nombor dan menghapuskan semua bukan- bilangan prima dengan menandakannya sebagai komposit. Untuk tugasan ini, kita boleh menggunakan BitSet untuk mewakili set nombor perdana, dengan setiap bit sepadan dengan nombor dalam julat.

Di bawah ialah pelaksanaan Java bagi kaedah penjanaan nombor perdana yang elegan dan cekap ini:

<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>

Kaedah ini menjana sejuta prima pertama dengan cekap dalam kira-kira satu saat pada komputer riba biasa. Gabungan ketepatan dan kelajuan menjadikannya alat yang berharga untuk menjana nombor perdana dalam pelbagai senario pengkomputeran.

Atas ialah kandungan terperinci Bagaimanakah Kita Boleh Menjana Nombor Perdana dengan Cekap?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!