Saringan Sundarama

Saringan Sundarama dalam jaringan diwakili oleh sejumlah besar sumber informasi latar belakang singkat. Namun demikian, saya memutuskan untuk menyatakan apa yang ingin saya baca di awal studi tentang algoritma bilangan-teoretis.

Saringan Sundarama adalah salah satu dari tiga metode paling terkenal untuk menghasilkan bilangan prima. Sekarang sudah biasa memperlakukannya sebagai beberapa eksotis karena kompleksitas komputasi yang buruk: O (N (logN)). Namun, asimptotik adalah asimptotik, dan dalam praktiknya, dalam kisaran pengayakan 32-bit, Atkin, misalnya, menyalip Sundaram hanya dengan optimasi yang cermat.

Implementasi saringan Atkin, yang beredar di Internet, tidak melampaui saringan Sundaram baik dari segi waktu, maupun dalam efisiensi memori. Jadi metode Sundaram dapat digunakan sebagai alat bantu dalam percobaan dengan algoritma yang lebih maju.

Saringan Sundarama menemukan semua bilangan prima dalam kisaran bilangan alami 3 ≤ n ≤ N "menyaring" komponen. Tanpa kehilangan keumuman, nilai N dapat dianggap aneh. Jika N adalah genap, maka dijamin komposit, dan dapat dikecualikan dari rentang pengayakan dengan mengurangi nilai batas atas oleh satu.

Algoritma didasarkan pada fakta berikut. Setiap bilangan komposit ganjil dapat direpresentasikan sebagai produk dari dua bilangan ganjil alami yang lebih besar dari satu:

(1) n = (2 * i + 1) * (2 * j + 1),

di mana i dan j adalah bilangan asli (nol bukan bilangan alami). Tidak mungkin untuk membayangkan bilangan prima n dalam bentuk ini, karena jika tidak maka akan berarti bahwa n memiliki pembagi tambahan selain dirinya dan satu.

Kami menulis n ganjil dalam bentuk 2 * m + 1, menggantikannya dengan (1), dan mendapatkan ekspresi untuk m:

(2) m = 2 * i * j + i + j.

Transformasi ini secara langsung mengarah pada gagasan saringan Sundaram.

Untuk menghilangkan angka komposit dari interval yang diberikan, Anda harus menggunakan array di mana elemen dengan indeks m adalah perwakilan dari angka 2 * m + 1. Setelah mengatur penghitungan nilai dari variabel i dan j, kami akan menghitung indeks m dengan rumus (2), dan sesuai elemen array menetapkan tanda "angka komposit". Setelah enumerasi selesai, semua angka komposit dalam rentang akan ditandai, dan bilangan prima dapat dipilih dengan tidak adanya tanda.

Masih mengklarifikasi detail teknis.

Berdasarkan alasan sebelumnya, untuk mewakili batas atas (ganjil) dari rentang saringan N, indeks m mengasumsikan nilai maksimumnya mmax = (N - 1) / 2. Ini menentukan ukuran array yang diperlukan.

Kami akan menghitung nilai-nilai i dan j dalam dua siklus: loop luar untuk menghitung nilai-nilai i, dan loop batin bersarang untuk nilai-nilai j.

Nilai awal dari penghitung loop eksternal adalah i = 1. Mengingat simetri lengkap dari terjadinya variabel i dan j dalam ekspresi (2), untuk menghindari perhitungan duplikat berulang, siklus dalam harus dimulai dengan nilai j = i.

Temukan nilai maksimum untuk penghitung loop eksternal imax ≥ i. Jika batas rentang N adalah angka komposit ganjil, maka dengan nilai i = imax, loop dalam harus dieksekusi setidaknya sekali dengan nilai parameternya j = imax untuk menghapus N, dan ekspresi (2) akan mengambil nilai maksimumnya:

mmax = 2 * imax * imax + imax + imax,
imax ^ 2 + imax - mmax / 2 = 0.

Memecahkan persamaan kuadratik ini, kita mendapatkan: imax = (√ (2 * mmax + 1) -1) / 2 = (√N-1) / 2.
Batasan untuk penghitung siklus dalam jmax ≥ j ditemukan dari ketidaksetaraan
mmax ≥ 2 * i * j + i + j , dari mana kita dapatkan: jmax = (mmax - i) / (2 * i + 1).

Nilai-nilai batas atas harus dibulatkan ke nilai keseluruhan terdekat, membuang bagian fraksional.

Berikut ini adalah daftar kelas C # Sundaram yang sangat sederhana yang mengimplementasikan metode yang dijelaskan.

using System; using System.Collections; namespace CSh_Sundaram { public class Sundaram { public double dt; //   () private long t1; //   private long t2; //   private uint limit; //     private int arrlength; //   private BitArray Prim; //    private int counter; public Sundaram(uint _limit) { limit = _limit; if (limit % 2 == 0) limit -= 1; arrlength = (int)(limit / 2); Prim = new BitArray(arrlength); t1 = DateTime.Now.Ticks; Sieve(); //  t2 = DateTime.Now.Ticks; dt = (double)(t2 - t1) / 10000000D; counter = -1; } public uint NextPrime { get { while (counter < arrlength - 1) { counter++; if (!Prim[counter]) return (uint)(2 * counter + 3); } return 0; } } private void Sieve() { int imax = ((int)Math.Sqrt(limit) - 1) / 2; for (int i = 1; i <= imax; i++) { int jmax = (arrlength - i) / (2 * i + 1); for (int j = i; j <= jmax; j++) { Prim[2 * i * j + i + j - 1] = true; } } } } } 

Sebagai parameter saat membuat objek bertipe Sundaram, batas atas rentang pengayakan ditunjukkan. Untuk menyaring, kelas menggunakan array bertipe BitArray. Ini meningkatkan runtime, tetapi memungkinkan Anda untuk mencakup seluruh rentang 32-bit dari jenis uint. Penyaringan dilakukan ketika mengakses metode Saringan () dari konstruktor kelas. Setelah selesai, bidang dt akan berisi waktu eksekusi Saringan dalam hitungan detik.

Saat mengakses properti NextPrime, secara berurutan, mulai dari 3, dalam urutan menaik, bilangan prima akan dikembalikan. Setelah semua yang sederhana dari rentang habis, nilai 0 akan dikembalikan.