Bagaimana untuk Memetakan Nombor Perdana dengan Cekap dalam Julat?

Memetakan Nombor Perdana dengan Cekap dalam Julat

Menentukan nombor perdana dalam julat yang ditentukan ialah tugas pengaturcaraan biasa. Untuk mengoptimumkan penggunaan memori untuk tugas ini, kami mencari algoritma yang mencipta struktur data paling padat yang mewakili nombor perdana untuk julat tertentu (1, N].

Algoritma Cadangan untuk Pemetaan Julat Perdana

Algoritma yang paling berkesan untuk ujian utama am ialah algoritma AKS Walau bagaimanapun, untuk tujuan praktikal dalam julat terhad, varian algoritma O(sqrt(N)) klasik berikut boleh menyediakan penyelesaian yang cekap:

def isprime(n):
    if n == 2 or n == 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    # Check prime divisors of the form 6k - 1 and 6k + 1
    i = 5
    w = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += w
        w = 6 - w
    return True

Analisis Algoritma

Algoritma ini bergantung pada fakta bahawa semua nombor perdana yang lebih besar daripada 3 adalah sama ada dalam bentuk 6k - 1 atau 6k 1. Dengan melelaran melalui pembahagi perdana yang berpotensi dalam corak ini, algoritma mengenal pasti nombor bukan perdana dengan cekap.

Pertimbangan Tambahan

Untuk lebih kelajuan, terutamanya apabila julat terhad , melaksanakan ujian pseudo-prima berdasarkan teorem kecil Fermat boleh berkesan Walau bagaimanapun, pendekatan ini mempunyai had julat.

Pengoptimuman Utama

Pengoptimuman yang paling ketara dalam. algoritma ini adalah penyingkiran semua nombor genap sebagai potensi perdana. Pengoptimuman ini mengurangkan dengan ketara bilangan semakan yang diperlukan, yang membawa kepada prestasi yang lebih baik.

Atas ialah kandungan terperinci Bagaimana untuk Memetakan Nombor Perdana dengan Cekap dalam Julat?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!