Bagaimanakah anda cekap mencari nombor perdana dalam julat tertentu?

Mencari Nombor Perdana dalam Julat Diberi

Dalam matematik, nombor perdana ialah nombor bulat yang lebih besar daripada 1 yang tidak boleh dibahagikan dengan mana-mana nombor lain kecuali 1 dan nombor itu sendiri. Mencari nombor perdana dalam julat tertentu boleh menjadi tugas pengaturcaraan biasa. Berikut ialah penjelasan terperinci tentang cara mendekati masalah ini dalam JavaScript:

Pendekatan Brute Force

Coretan kod yang disediakan cuba mencari nombor perdana antara 0 dan 100 menggunakan pendekatan brute force. Ia menyemak sama ada nombor itu boleh dibahagikan dengan mana-mana nombor dari 2 hingga 12 dan mengembalikan nombor itu jika tiada pembahagi ditemui. Walau bagaimanapun, pendekatan ini mempunyai beberapa kelemahan:

• Ia tidak cekap, terutamanya untuk julat yang lebih besar.
• Sukar untuk melanjutkan untuk mencari bilangan nombor perdana bagi julat yang lebih besar.

Ayak Eratosthenes

Algoritma yang lebih cekap untuk mencari nombor perdana dipanggil Ayak Eratosthenes. Begini caranya:

1. Buat tatasusunan dipanggil ayak dengan panjang maksimum 1.
2. Mulakan semua elemen dalam tatasusunan kepada palsu (dengan mengandaikan palsu bermakna nombor itu adalah perdana).
3. Lelar melalui tatasusunan ayak daripada 2 kepada punca kuasa dua maks.
4. Untuk setiap nombor perdana i, tandakan semua gandaannya sebagai bukan perdana dengan menetapkan ayak[i j] kepada benar untuk semua j daripada i j hingga maks.
5. Selepas lelaran, nombor yang tidak bertanda dalam tatasusunan ayak ialah nombor perdana.

Dalam JavaScript, kod untuk Sieve of Eratosthenes kelihatan seperti ini:

<code class="js">function getPrimes(max) {
    var sieve = [], i, j, primes = [];
    for (i = 2; i <= max; ++i) {
        if (!sieve[i]) {
            // i has not been marked -- it is prime
            primes.push(i);
            for (j = i << 1; j <= max; j += i) {
                sieve[j] = true;
            }
        }
    }
    return primes;
}</code>

Pendekatan ini mempunyai kerumitan masa O(n log log n), yang jauh lebih cekap daripada pendekatan brute force.

Atas ialah kandungan terperinci Bagaimanakah anda cekap mencari nombor perdana dalam julat tertentu?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!