Bagaimanakah Saya Boleh Menjana Nombor Perdana dengan Anggun di Jawa Menggunakan Penapis Eratosthenes?

Ayak Eratosthenes di Jawa: Hasilkan nombor perdana dengan elegan

Pengenalan

Penjanaan nombor perdana ialah masalah asas dalam sains komputer, dengan pelbagai algoritma untuk dipilih. Antaranya, penapis Eratosthenes terkenal dengan kesederhanaan dan kecekapannya. Artikel ini menyediakan pelaksanaan Java yang elegan yang menggunakan penapis Eratosthenes untuk menjana n nombor perdana pertama.

Ayak Eratosthenes

Ayak Eratosthenes ialah algoritma probabilistik yang mengenal pasti nombor perdana dengan menghapuskan gandaan nombor perdana secara berulang. Ia mula-mula memulakan tatasusunan bendera boolean, setiap bendera mewakili nombor sehingga had yang ditentukan. Algoritma kemudian melelar melalui tatasusunan bermula dengan nombor perdana pertama 2 dan menandakan semua gandaan itu sebagai bukan perdana. Proses ini berterusan sehingga semua nombor dalam had telah dihapuskan, hanya meninggalkan nombor perdana.

Pelaksanaan yang elegan

Pelaksanaan Java yang elegan bagi Sieve of Eratosthenes kelihatan seperti ini:

public static BitSet computePrimes(int limit) {
    final BitSet primes = new BitSet();
    primes.set(0, false);
    primes.set(1, false);
    primes.set(2, limit, true);
    for (int i = 2; i * i <= limit; i++) {
        if (primes.get(i)) {
            for (int j = i * i; j <= limit; j += i) {
                primes.set(j, false);
            }
        }
    }
    return primes;
}

Penerangan

Pelaksanaan ini mencipta BitSet di mana setiap bit mewakili nombor sehingga had yang ditentukan. Pada mulanya, 0 dan 1 ditandakan sebagai bukan perdana dan semua nombor lain ditandakan sebagai perdana.

Gelung luar berulang melalui tatasusunan bermula dari nombor perdana pertama 2. Jika bit pada kedudukan semasa ditetapkan (menunjukkan bahawa ia adalah perdana), gelung dalam menandakan semua gandaan nombor perdana itu sebagai bukan perdana. Proses ini berterusan sehingga semua nombor dalam had telah dihapuskan.

Akhir sekali, kembalikan BitSet yang mengandungi nombor perdana.

Kesimpulan

Pelaksanaan Java Sieve of Eratosthenes ini menunjukkan keanggunan dan kesederhanaan algoritma. Ia menjana nombor perdana dengan cekap dan mempunyai struktur logik yang jelas. Kod ini dioptimumkan untuk prestasi dan kefahaman, menjadikannya alat yang berharga untuk pengaturcara yang memerlukan penjana nombor perdana.

Atas ialah kandungan terperinci Bagaimanakah Saya Boleh Menjana Nombor Perdana dengan Anggun di Jawa Menggunakan Penapis Eratosthenes?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!