Bagaimanakah Kita Boleh Mencari Semua Nombor Perdana Dengan Cekap Dalam Julat Yang Diberikan?

Mencari Nombor Perdana dalam Julat Diberi: Pendekatan Dioptimumkan

Artikel ini menangani cabaran mengenal pasti semua nombor perdana dengan cekap dalam julat tertentu. Nombor perdana, mengikut takrifan, ialah nombor asli yang lebih besar daripada 1 yang tidak mempunyai pembahagi positif selain daripada 1 dan dirinya sendiri.

Pendekatan Cacat dan Pembetulannya

Percubaan awal untuk menyelesaikan masalah ini mengandungi kecacatan kritikal dalam logiknya. Kod itu berulang daripada 0, salah memasukkan 0 dan 1 sebagai potensi bilangan prima, dan menggunakan ujian primaliti yang salah. Keadaan if (i != j && i % j == 0) mengenal pasti nombor komposit, bukan nombor perdana. Pendekatan yang betul melibatkan menyemak sama ada nombor tidak boleh dibahagi dengan mana-mana nombor selain 1 dan nombor itu sendiri.

Penyelesaian Dioptimumkan menggunakan Ayak Bahagian Percubaan

Kaedah yang jauh lebih cekap menggunakan penapis bahagian percubaan. Pendekatan ini memanfaatkan beberapa pengoptimuman utama:

1. Had Punca Kuasa Dua: Kita hanya perlu menguji kebolehbahagi sehingga punca kuasa dua nombor sasaran. Jika suatu nombor mempunyai pembahagi yang lebih besar daripada punca kuasa duanya, ia juga mesti mempunyai pembahagi yang lebih kecil daripada punca kuasa duanya.

2. Penyingkiran Berbilang: Sebaik sahaja nombor perdana dikenal pasti, gandaannya dialih keluar daripada senarai calon, dengan ketara mengurangkan bilangan semakan seterusnya.

3. Anggaran Lelaran: Kod menggunakan formula anggaran (π(x)

Kod yang dioptimumkan (menggunakan LINQ untuk ringkas) melaksanakan strategi ini dengan berkesan:

Enumerable.Range(0, Math.Floor(2.52*Math.Sqrt(num)/Math.Log(num))).Aggregate(
    Enumerable.Range(2, num-1).ToList(), 
    (result, index) => { 
        var bp = result[index]; var sqr = bp * bp;
        result.RemoveAll(i => i >= sqr && i % bp == 0); 
        return result; 
    }
);

Algoritma yang diperhalusi ini memberikan peningkatan prestasi yang ketara berbanding dengan pendekatan naif, terutamanya apabila berurusan dengan julat yang luas. Penggunaan Enumerable.Range, ToList, RemoveAll dan Aggregate membolehkan pelaksanaan yang padat dan cekap.

Atas ialah kandungan terperinci Bagaimanakah Kita Boleh Mencari Semua Nombor Perdana Dengan Cekap Dalam Julat Yang Diberikan?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!