Saringan Eratosthenes di luar O (n). Bukti

Dalam komentar ke salah satu posting sebelumnya tentang saringan Eratosthenes, algoritma singkat dari Wikipedia ini disebutkan:

Algoritma 1:

1:  i := 2, 3, 4, ...,  n: 2:  lp[i] = 0: 3: lp[i] := i 4: pr[] += {i} 5:  p  pr  p ≤ lp[i]  p*i ≤ n: 6: lp[p*i] := p : lp -        n pr -     n. 

Algoritma itu sederhana, tetapi tidak bagi semua orang yang terlihat jelas. Masalah utama adalah bahwa tidak ada bukti di Wikipedia, dan tautan ke sumber ( pdf ) berisi algoritma yang agak berbeda dari yang di atas.

Dalam posting ini saya akan mencoba, saya harap, dimungkinkan untuk membuktikan bahwa algoritma ini tidak hanya berfungsi, tetapi juga untuk kompleksitas linier.

Definisi

$$$\ mathcal {P}$ - Banyak bilangan prima.
$$$lp (x)$ - pembagi prime minimum nomor: $$$lp (x) = min \ {p \ in \ mathcal {P} \ \ vert \ p \ vert x \}$
$$$rd (x)$ - faktor lain: $$$rd (x) = x / lp (x)$

Harap dicatat bahwa semua definisi di atas adalah untuk $$$x \ ge 2$ .

Beberapa sifat yang jelas dari fungsi yang diperkenalkan di atas, yang akan digunakan kemudian:
$$$lp (a \ kali b) = min (lp (a), lp (b))$
$$$rd (x) <x$
$$$p \ in \ mathcal {P} => lp (p) = p$

Bukti

Lemma 1 : $$$lp (x) \ le lp (rd (x)), \ forall x \ notin \ mathcal {P}, x> 1$
Bukti : Karena pembagi apapun $$$rd (x)$ juga pembagi $$$x$ , dan $$$lp (x)$ tidak lebih unggul dari pembagi apa pun $$$x$ lalu $$$lp (x)$ tidak melebihi pembagi apa pun $$$rd (x)$ termasuk yang terkecil dari mereka. Satu-satunya masalah dengan pernyataan ini adalah jika $$$rd (x)$ tidak memiliki pembagi sederhana, tetapi ini hanya mungkin jika $$$x \ in \ mathcal {P}$ , yang dikecualikan dalam kondisi lemma.
$$$\ persegi$

Biarkan $$$E = \ {(lp (x), rd (x)) \ vert \ forall x \ notin \ mathcal {P}, 2 \ le x \ le n \}$

Karena $$$lp (x) \ kali rd (x) = x$ (menurut definisi $$$rd ()$ ), jika kita diberi banyak $$$E$ maka kita bisa menghitung $$$lp ()$ untuk semua bilangan komposit hingga n. Ini dilakukan, misalnya, dengan algoritma berikut:

Algoritma 2:

 1:   (l,r)  E: 2: lp[l*r] := l; 

Catat itu $$$\ vert E \ vert \ le n$ Oleh karena itu algoritma 2 di atas berfungsi untuk kompleksitas linier.

Lebih lanjut, saya akan membuktikan bahwa algoritma 1 dari Wikipedia sebenarnya hanya mengulangi semua elemen dari set ini, karena dapat diparameterisasi dengan cara yang berbeda.

Biarkan $$$E '= \ {(p, r) \ vert p \ dalam \ mathcal {P}, 2 \ le r <n, p \ le lp (r), p \ kali r \ le n \}$

Lemma 2 : $$$E = E '$
Bukti :

Biarkan $$$(a, b) \ dalam E$ => $$$\ ada x \ notin \ mathcal {P}, \ 2 \ le x \ le n \ mid a = lp (x), b = rd (x)$ .

Menurut definisi $$$lp (), rd ()$ : $$$a \ in \ mathcal {P}$ , $$$a \ kali b = x$ . Oleh Lemma 1, $$$a \ le lp (b)$ .
karena $$$rd (x) <x$ lalu $$$b <n$ .
Sejak $$$x \ notin \ mathcal {P}$ , $$$b \ ge 2$ .
Juga, menurut definisi $$$E$ , $$$x \ le n$ oleh karena itu $$$a \ kali b \ le n$ .
Semua 4 kondisi $$$E$ berarti terpenuhi $$$(a, b) \ dalam E '$ => $$$E \ subset E '$ .

Biarkan $$$(a, b) \ dalam E '$ . Biarkan $$$x = a \ kali b$ .
Menurut definisi $$$E$ , $$$a \ in \ mathcal {P}$ . Berarti $$$a$ - membagi sederhana $$$x$ .
$$$lp (x) = lp (a \ kali b) = min (lp (a), lp (b)) = min (a, lp (b)).$
Karena $$$a \ le lp (b)$ lalu $$$lp (x) = a.$ Berarti $$$b = rd (x).$
Menurut definisi, $$$x = a \ kali b \ le n.$ Jelas juga $$$x = a \ kali b \ ge 2.$
Semua ketentuan untuk $$$E$ selesai => $$$E '\ subset E.$

Oleh karena itu $$$E = E '.$
$$$\ persegi$

Sekarang tinggal memilah yang benar $$$r$ dan $$$p$ dari definisi himpunan $$$E$ dan terapkan Algoritma 2. Inilah yang dilakukan oleh Algoritma 1 (hanya variabel i yang digunakan, bukan r). Tapi ada masalah! Untuk memilah-milah semua elemen set $$$E$ untuk menghitung $$$lp,$ kita perlu tahu $$$lp,$ karena ada syarat dalam definisi $$$p \ le lp (r)$ .

Untungnya, masalah ini dapat diurutkan dengan benar. Perlu untuk memilah $$$r$ di lingkaran luar, dan $$$p$ - di dalam. Lalu $$$lp (r)$ sudah akan dihitung. Fakta ini dibuktikan oleh teorema berikut.

Teorema 1:
Algoritma 1 mendukung invarian berikut: Setelah iterasi loop luar untuk i = k, semua bilangan prima hingga k inklusif akan disorot dalam pr. Juga akan dihitung $$$lp ()$ untuk semua $$$x \ notin \ mathcal {P} \ mid x \ le n, \ rd (x) \ le k$ dalam lp array.

Bukti :
Kami membuktikan dengan induksi. Untuk k = 2, invarian diperiksa secara manual. Satu-satunya prime 2 akan ditambahkan ke daftar pr, karena lp [] array awalnya diisi dengan nol. Juga, satu-satunya nomor majemuk di mana $$$rd (x) \ le 2$ - ini 4. Mudah untuk memverifikasi bahwa loop dalam akan mengeksekusi tepat sekali (untuk n> 3) dan mengeksekusi lp [4] dengan benar: = 2.

Sekarang anggaplah bahwa invarian berlaku untuk iterasi i = k-1. Mari kita buktikan bahwa itu juga akan berlaku untuk iterasi i = k.

Untuk melakukan ini, cukup untuk memeriksa apakah nomor i, jika prima, akan ditambahkan ke daftar pr dan itu $$$lp ()$ akan dihitung untuk semua angka komposit $$$x \ le n,$ termasuk $$$rd (x) = i.$ Ini adalah angka-angka dari invarian untuk k yang belum dicakup oleh invarian untuk k-1.

Jika saya sederhana, maka lp [i] akan menjadi 0, karena satu-satunya operasi penulisan ke array lp, yang secara teoritis dapat menghitung lp [i] (pada baris 6), selalu menulis ke indeks komposit, karena p * i (untuk i> 1) - selalu majemuk. Oleh karena itu, nomor i akan ditambahkan ke daftar bilangan prima. Juga, pada baris 3, lp [i] akan dihitung.

Jika i adalah komposit, maka pada awal iterasi lp [i] sudah akan dihitung oleh invarian untuk i = k-1, karena $$$rd (i) <i$ atau $$$rd (i) \ le i-1,$ oleh karena itu, saya jatuh dalam kondisi invarian dalam iterasi sebelumnya. Oleh karena itu, angka gabungan i tidak akan ditambahkan ke daftar bilangan prima.

Selanjutnya, memiliki lp [i] yang benar dan semua bilangan prima hingga i inklusif, loop pada baris 5-6 akan beralih ke semua elemen $$$(p, i) \ dalam E '$ di mana bagian kedua adalah saya:

• $$$p \ dalam P,$ karena dari daftar pr
• $$$p \ le lp (i),$ oleh kondisi untuk menghentikan siklus
• $$$p \ kali i \ le n,$ oleh kondisi untuk menghentikan siklus
• $$$i <n,$ mengikuti dari $$$p \ kali i \ le n, \ p> 1$

Semua bilangan prima yang diperlukan dalam daftar pr adalah, karena hanya nomor hingga $$$lp (i) \ le i$ . Oleh karena itu, nilai lp [] akan dihitung untuk semua bilangan komposit $$$x$ untuk itu $$$rd (x) = i$ . Ini persis semua angka yang hilang selama transisi dari invarian untuk k-1 ke invarian untuk k.

Oleh karena itu, invarian berlaku untuk i = 2..n.

$$$\ persegi$

Dengan invarian dari Teorema 1 untuk i = n ternyata semua bilangan prima hingga n dan semua lp [] akan dihitung dengan algoritma 1.

Selain itu, karena di baris 5-6 berbagai elemen dari himpunan diurutkan $$$E$ , maka total inner loop tidak akan dieksekusi lagi $$$\ vert E \ vert <n$ operasi. Operasi pemeriksaan dalam loop akan berjalan dengan lancar $$$\ vert E \ vert + n - 1 <2n$ kali ( $$$\ vert E \ vert$ kali akan mengembalikan true dan n-1 kali, untuk setiap i, akan mengembalikan false). Semua operasi yang tersisa bersarang dalam satu siklus di i dari 2 hingga n.
Maka kompleksitas algoritma 1 adalah O (n).