Tapis Atkin - Riwayat revisi

Maintenance script: Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

2026-08-25T14:01:38Z

Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

@@ Baris 1: / Baris 1: @@
-Dalam [[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.
+Dalam [[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.<ref>A. O. L. Atkin, D. J. Bernstein, [http://www.ams.org/mcom/2004-73-246/S0025-5718-03-01501-1/S0025-5718-03-01501-1.pdf ''Perdana saringan menggunakan biner bentuk kuadrat''], Matematika. Comp. '''73''' (2004), 1023-1030.</ref>
 == Algoritma ==
@@ Baris 12: / Baris 12: @@
 # Buat daftar saringan dengan entri untuk setiap bilangan bulat positif; semua entri dari daftar ini pada awalnya harus ditandai non prime (komposit).
 # Untuk setiap nomor entri  dalam daftar saringan, dengan sisa modulo-enam puluh :
-## Jika adalah 1, 13, 17, 29, 37, 41, 49, atau 53, balikkan entri untuk setiap kemungkinan solusi ke .  Jumlah operasi pembalikan sebagai rasio terhadap kisaran penyaringan untuk pendekatan langkah ini  ×  (angka "8" dalam pecahan berasal dari delapan modulos yang ditangani oleh kuadrat ini dan 60 karena Atkin menghitungnya berdasarkan jumlah genap modulo 60 roda), yang menghasilkan pecahan sekitar 0.1117010721276....
+## Jika adalah 1, 13, 17, 29, 37, 41, 49, atau 53, balikkan entri untuk setiap kemungkinan solusi ke .  Jumlah operasi pembalikan sebagai rasio terhadap kisaran penyaringan untuk pendekatan langkah ini <ref>A. O. L. Atkin, D. J. Bernstein, [http://www.ams.org/mcom/2004-73-246/S0025-5718-03-01501-1/S0025-5718-03-01501-1.pdf ''Perdana saringan menggunakan biner bentuk kuadrat''], Matematika. Comp. '''73''' (2004), 1023-1030.</ref> ×  (angka "8" dalam pecahan berasal dari delapan modulos yang ditangani oleh kuadrat ini dan 60 karena Atkin menghitungnya berdasarkan jumlah genap modulo 60 roda), yang menghasilkan pecahan sekitar 0.1117010721276....
-## Jika adalah 7, 19, 31, atau 43, balikkan entri untuk setiap solusi yang mungkin ke .  Jumlah operasi pembalikan sebagai rasio terhadap kisaran penyaringan untuk pendekatan langkah ini  ×  (angka "4" dalam pecahan berasal dari empat modulos yang ditangani oleh kuadrat ini dan 60 karena Atkin menghitungnya berdasarkan jumlah genap modulo 60 roda), yang menghasilkan pecahan sekitar 0,072551974569....
+## Jika adalah 7, 19, 31, atau 43, balikkan entri untuk setiap solusi yang mungkin ke .  Jumlah operasi pembalikan sebagai rasio terhadap kisaran penyaringan untuk pendekatan langkah ini <ref>A. O. L. Atkin, D. J. Bernstein, [http://www.ams.org/mcom/2004-73-246/S0025-5718-03-01501-1/S0025-5718-03-01501-1.pdf ''Perdana saringan menggunakan biner bentuk kuadrat''], Matematika. Comp. '''73''' (2004), 1023-1030.</ref> ×  (angka "4" dalam pecahan berasal dari empat modulos yang ditangani oleh kuadrat ini dan 60 karena Atkin menghitungnya berdasarkan jumlah genap modulo 60 roda), yang menghasilkan pecahan sekitar 0,072551974569....
-## Jika adalah 11, 23, 47, atau 59, balikkan entri untuk setiap kemungkinan solusi ke  jika .  Jumlah operasi pembalikan sebagai rasio terhadap kisaran penyaringan untuk pendekatan langkah ini  ×  (angka "4" dalam pecahan berasal dari empat modulos yang ditangani oleh kuadrat ini dan 60 karena Atkin menghitungnya berdasarkan jumlah genap modulo 60 roda), yang menghasilkan sebagian kecil sekitar 0,060827679704....
+## Jika adalah 11, 23, 47, atau 59, balikkan entri untuk setiap kemungkinan solusi ke  jika .  Jumlah operasi pembalikan sebagai rasio terhadap kisaran penyaringan untuk pendekatan langkah ini <ref>A. O. L. Atkin, D. J. Bernstein, [http://www.ams.org/mcom/2004-73-246/S0025-5718-03-01501-1/S0025-5718-03-01501-1.pdf ''Perdana saringan menggunakan biner bentuk kuadrat''], Matematika. Comp. '''73''' (2004), 1023-1030.</ref> ×  (angka "4" dalam pecahan berasal dari empat modulos yang ditangani oleh kuadrat ini dan 60 karena Atkin menghitungnya berdasarkan jumlah genap modulo 60 roda), yang menghasilkan sebagian kecil sekitar 0,060827679704....
 ## Jika adalah sesuatu yang lain, abaikan sepenuhnya.
 # Mulailah dengan angka terendah dalam daftar tapis.
@@ Baris 25: / Baris 25: @@
 == Kode semu ==
-Berikut ini adalah [[kode semu]] yang '''menggabungkan''' algoritma Atkin 3.1, 3.2, dan 3.3 dengan menggunakan '''gabungan''' set "s" dari semua bilangan modulo 60 tidak termasuk yang merupakan kelipatan dari bilangan prima 2, 3, dan 5, sesuai dengan algoritma, 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
+<syntaxhighlight lang="c">
 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 [[Faktorisasi roda |faktor roda]] (2/3/5) [[tapis Eratosthenes]].  Untuk meningkatkan efisiensinya, suatu metode harus dirancang untuk meminimalkan atau menghilangkan perhitungan takproduktif ini.
@@ Baris 38: / Baris 75: @@
 == Referensi ==
+<references />
 == Sumber dan atribusi ==
 Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Tapis+Atkin&oldid=28421933 Wikipedia bahasa Indonesia], revisi 28421933 (2025-11-12T07:15:32Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.

Maintenance script: Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 28421933; atribusi sumber disertakan.

2026-08-25T13:27:14Z

Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 28421933; atribusi sumber disertakan.

Halaman baru

Dalam [[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.

== Algoritma ==
Dalam algoritma:
* Semua sisanya adalah [[Operasi modulo |modulo]], enam puluh sisa (bagi nomor dengan 60 dan kembalikan sisanya).
* Semua angka, termasuk dan , adalah [[Bilangan asli|bilangan bulat positif]].
* Membalik entri dalam daftar tapis berarti mengubah tanda (prima atau nonprima) ke tanda yang berlawanan.
* Ini menghasilkan bilangan dengan bilangan ganjil solusi ke persamaan yang sesuai berpotensi menjadi bilangan prima (bilangan prima jika juga bebas kuadrat), dan bilangan dengan bilangan genap solusi yang digabungkan.

Algoritma:
# Buat daftar hasil, diisi dengan 2, 3, dan 5.
# Buat daftar saringan dengan entri untuk setiap bilangan bulat positif; semua entri dari daftar ini pada awalnya harus ditandai non prime (komposit).
# Untuk setiap nomor entri dalam daftar saringan, dengan sisa modulo-enam puluh :
## Jika adalah 1, 13, 17, 29, 37, 41, 49, atau 53, balikkan entri untuk setiap kemungkinan solusi ke . Jumlah operasi pembalikan sebagai rasio terhadap kisaran penyaringan untuk pendekatan langkah ini × (angka "8" dalam pecahan berasal dari delapan modulos yang ditangani oleh kuadrat ini dan 60 karena Atkin menghitungnya berdasarkan jumlah genap modulo 60 roda), yang menghasilkan pecahan sekitar 0.1117010721276....
## Jika adalah 7, 19, 31, atau 43, balikkan entri untuk setiap solusi yang mungkin ke . Jumlah operasi pembalikan sebagai rasio terhadap kisaran penyaringan untuk pendekatan langkah ini × (angka "4" dalam pecahan berasal dari empat modulos yang ditangani oleh kuadrat ini dan 60 karena Atkin menghitungnya berdasarkan jumlah genap modulo 60 roda), yang menghasilkan pecahan sekitar 0,072551974569....
## Jika adalah 11, 23, 47, atau 59, balikkan entri untuk setiap kemungkinan solusi ke jika . Jumlah operasi pembalikan sebagai rasio terhadap kisaran penyaringan untuk pendekatan langkah ini × (angka "4" dalam pecahan berasal dari empat modulos yang ditangani oleh kuadrat ini dan 60 karena Atkin menghitungnya berdasarkan jumlah genap modulo 60 roda), yang menghasilkan sebagian kecil sekitar 0,060827679704....
## Jika adalah sesuatu yang lain, abaikan sepenuhnya.
# Mulailah dengan angka terendah dalam daftar tapis.
# Ambil bilangan berikutnya dalam daftar tapis yang masih bertanda prima.
# Sertakan nomor dalam daftar hasil.
# Kuadratkan angka tersebut dan tandai semua kelipatan persegi tersebut sebagai bukan prima. Perhatikan bahwa kelipatan yang dapat difaktorkan dengan 2, 3, atau 5 tidak perlu diberi tanda, karena ini akan diabaikan pada [[pencacahan]] akhir prima.
# Ulangi langkah empat sampai tujuh. Jumlah total operasi untuk pengulangan penandaan bilangan prima ini sebagai rasio rentang penyaringan adalah jumlah dari balikan bilangan prima yang dikuadratkan, yang mendekati [[fungsi zeta prima]] (2) dari 0,45224752004... minus , , dan untuk bilangan prima yang telah dieliminasi oleh roda, dengan hasil dikalikan dengan untuk rasio pukulan roda per rentang; ini menghasilkan rasio sekitar 0,01363637571....

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 semu ==

Berikut ini adalah [[kode semu]] yang '''menggabungkan''' algoritma Atkin 3.1, 3.2, dan 3.3 dengan menggunakan '''gabungan''' set "s" dari semua bilangan modulo 60 tidak termasuk yang merupakan kelipatan dari bilangan prima 2, 3, dan 5, sesuai dengan algoritma, 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

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 [[Faktorisasi roda |faktor roda]] (2/3/5) [[tapis Eratosthenes]]. Untuk meningkatkan efisiensinya, suatu metode harus dirancang untuk meminimalkan atau menghilangkan perhitungan takproduktif ini.

== Lihat pula ==
* [[Tapis Eratosthenes]]
* [[Tapis Legendre]]
* [[Tapis Sundaram]]
* [[Teori tapis]]

== Referensi ==

== Sumber dan atribusi ==

Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Tapis+Atkin&oldid=28421933 Wikipedia bahasa Indonesia], revisi 28421933 (2025-11-12T07:15:32Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.