|
Tapis AtkinDalam matematika, tapis Atkin adalah algoritme modern untuk menemukan semua bilangan prima sampai dengan bilangan bulat yang ditentukan. Dibandingkan dengan tapis Eratosthenes yang kuno, yang menandai kelipatan dari bilangan prima, Tapis Atkin melakukan beberapa pekerjaan awal dan kemudian menandai kelipatan kuadrat dari bilangan prima, sehingga mencapai teori kompleksitas asimtotik yang lebih baik. Tapis Atkin dibuat pada tahun 2003 oleh A. O. L. Atkin dan Daniel J. Bernstein.[1] AlgoritmaDalam algoritma:
Algoritme:
Menambahkan rasio operasi di atas bersama-sama, algoritma di atas mengambil rasio konstan dari operasi pembalikan / penandaan ke kisaran penyaringan sekitar 0.2587171021...; Dari implementasi aktual algoritma, rasionya sekitar 0,25 untuk rentang penyaringan serendah 67. Kode semuBerikut ini adalah kode semu yang menggabungkan algoritme Atkin 3.1, 3.2, dan 3.3[1] dengan menggunakan gabungan set "s" dari semua bilangan modulo 60 tidak termasuk yang merupakan kelipatan dari bilangan prima 2, 3, dan 5, sesuai dengan algoritme, untuk versi langsung dari algoritme yang mendukung pengemasan bit opsional pada roda; meskipun tidak disebutkan secara khusus dalam makalah referensi, kode semu ini menghilangkan beberapa kombinasi yang jelas dari ganjil /genap x / y untuk mengurangi komputasi di mana komputasi tersebut tidak akan pernah lulus tes modulo (yaitu akan menghasilkan angka genap limit ← 1000000000 // batas pencarian sembarang
// set posisi "hit" roda untuk roda 2/3/5 yang diputar dua kali sesuai algoritma Atkin ← {1,7,11,13,17,19,23,29,31,37,41,43,47,49,53,59}
// Inisialisasi saringan dengan roda yang cukup untuk memasukkan batas:
untuk n ← 60 × w + x dimana w ∈ {0,1,...,limit ÷ 60}, x ∈ s:
is_prime(n) ← false
// Masukkan bilangan prima kandidat:
// bilangan bulat yang memiliki jumlah ganjil
// representasi dengan bentuk kuadrat tertentu.
// Algoritme langkah 3.1:
for n ≤ limit, n ← 4x²+y² where x ∈ {1,2,...} and y ∈ {1,3,...} // all x's odd y's
if n mod 60 ∈ {1,13,17,29,37,41,49,53}:
is_prime(n) ← ¬is_prime(n) // toggle state
// Algoritme langkah 3.2:
for n ≤ limit, n ← 3x²+y² where x ∈ {1,3,...} and y ∈ {2,4,...} // only odd x's
if n mod 60 ∈ {7,19,31,43}: // and even y's
is_prime(n) ← ¬is_prime(n) // toggle state
// Algoritme langkah 3.3:
for n ≤ limit, n ← 3x²-y² where x ∈ {2,3,...} and y ∈ {x-1,x-3,...,1} //all even/odd
if n mod 60 ∈ {11,23,47,59}: // odd/even combos
is_prime(n) ← ¬is_prime(n) // toggle state
// Hilangkan komposit dengan pengayakan, hanya untuk kejadian di roda:
untuk n² ≤ limit, n ← 60 × w + x dimana w ∈ {0,1,...}, x ∈ s, n ≥ 7:
if is_prime(n):
// n adalah bilangan prima, hilangkan kelipatan kuadratnya; ini sudah cukup
// karena komposit bebas persegi tidak bisa masuk dalam daftar ini
for c ≤ limit, c ← n² × (60 × w + x) where w ∈ {0,1,...}, x ∈ s:
is_prime(c) ← false
// satu sapuan untuk menghasilkan daftar bilangan prima berurutan hingga batas:
output 2, 3, 5
for 7 ≤ n ≤ limit, n ← 60 × w + x where w ∈ {0,1,...}, x ∈ s:
if is_prime(n): output n
Kode semu ini ditulis untuk kejelasan; meskipun beberapa perhitungan yang berlebihan telah dihilangkan dengan mengontrol kombinasi ganjil / genap x / y, itu masih menyia-nyiakan hampir setengah dari komputasi kuadratnya pada gelung takproduktif yang tidak lulus uji modulo sedemikian rupa sehingga tidak akan lebih cepat dari yang setara faktor roda (2/3/5) tapis Eratosthenes. Untuk meningkatkan efisiensinya, suatu metode harus dirancang untuk meminimalkan atau menghilangkan perhitungan takproduktif ini. Lihat pulaReferensi |