Rehber Asal sayıları hızlı bulma: Sieve of Eratosthenes

Merhaba,

Dün binary search ile algoritma serisini başlatmışken bugün Sieve of Eratosthenes (Eratosten Kalburu) algoritmasıyla devam edeyim dedim. Seri dedim ama istikrar sağlar mıyım, orasını bilmiyorum. Hazır canım çekmişken bu algoritmaya da değineyim dedim. İyi okumalar.

Asal sayı ne ki hızlı bulalım?​

Asal sayılar, 1'den ve kendisinden başka bir pozitif tam sayıya bölünemeyen tam sayılardır; daha doğrusu tam olarak 2 pozitif bölene sahip olan sayılardır ve bu yüzden de mesela 1 asal sayı olarak kabul edilmez. En küçük asal sayı 2'dir çünkü pozitif tam sayılardan sadece 1 ve 2'ye bölünebilir. Asal sayılar 2, 3, 5, 7, 11,... diye devam eder. Tam sayıların asallığını tek tek kontrol ederek asal sayıları ayıklayabilirsiniz.

E işte dediğin gibi tek tek kontrol ederiz, olmaz mı?​

Olur olmasına da çok hızlı olmaz.

Elimizde bir n sayısı olsun. Bu sayının asallığını nasıl kontrol ederiz?

1'den n'e kadarki tüm tam sayıların n'i bölüp bölmediğine bakabiliriz. Eğer bu sayılar arasında n, 1 ve n dışındaki herhangi bir sayıya bölünebiliyorsa n asal değildir. n adet sayıyı kontrol etmiş oluyoruz ve dolayısıyla n işlem yapmış oluyoruz.

Çok detayına inmeden şöyle bir bilgi sunayım:

Ortalama bir bilgisayar, 100 milyon ila 1 milyar aritmetik işlemi yaklaşık 1 saniyede yapabilir.

Genişletmek için tıkla...

Küçültmek için tıkla...

Peki bu yöntemle mesela 1'den 1000'e kadarki asalları bulmak istesek toplam kaç işlem gerekirdi?
1'den n'e kadarki sayıların toplamı formülüyle (veya 1000'inci üçgensel sayı) 1 + 2 + 3 + ... + 1000 = 1000 * 1001 / 2 = 500500 işlem. E tamam, bu iyiymiş... İyi olmasına iyi de 1000 aslında biraz küçük bir sınır.

Gelin şunu bi' 1 milyona yükseltelim. Aslında toplam formülünün asıl değerine çok gerek yok, yaklaşık olarak sayının karesinin yarısı olarak düşünebilirsiniz; hatta yarısını düşünmeye bile gerek yok çünkü çok fark etmiyor. 1 milyonun karesi (10^6)^2 = 10^12 ediyor. Hmm, ne demiştik? En fazla 10^9 işlemi 1 saniyede yapabiliyorduk. 10^12 bunun 1000 katı, yani yaklaşık 1000 saniye sürecek (işlem sayısıyla süre yaklaşık olarak doğru orantılı).

Yani, 1000 saniyenin ne kadar uzun bir süre olduğu tartışılabilir. Peki sınırı 10 milyona yükseltseydik? Karesi 10^14, bir öncekinin 100 katı. Süre de 100 katına çıkıp 10.000 saniye olurdu. Yaklaşık olarak 2.8 saat ediyor, sizi bilmem ama bence fazla uzun.

Burada işleri biraz daha hızlandıran bir yöntem var: n sayısının asallığı için n'e kadarki tüm pozitif sayıları kontrol ediyorduk ya, n - 1'e kadar kont- şaka şaka. kök(n)'e kadar kontrol edebiliriz.

Neden mi?

n sayısının bir pozitif böleni a olsun. Bunun gereği olarak bir b böleni daha olması gerekir ki a * b = n olsun. Dikkat edin ki bu bölenlerden biri kök(n)'den büyükse diğeri küçüktür. İşte bu sayede kökten büyük sayıları göz ardı edebiliriz.

Bu yolla 10 milyona kadarki sayılar için toplam yaklaşık 2 * 10^10 işlem gerekir:

Evet... Yine de kodunu ve hız testini paylaşayım:
[CODE lang="cpp" title="1'den n'e kadarki asalların sayısını bulma (pek optimize değil)"]#include <bits/stdc++.h>
using namespace std;

bool asal_mi(int n) {
// 2'den küçük sayılar için.
if (n <= 1)
return false;

for (int i = 2; i * i <= n; i++) {
// 2'den kök(n)'e kadarki herhangi bir sayıya bölünebiliyorsa n asal değildir.
// Burada ilk böleni bulduğumuz an direkt false döndürdüğümüz için aslında
// biraz daha optimize oluyor. Hep kök(n)'e kadar ilerleseydik daha uzun sürerdi.
if (n % i == 0)
return false;
}

// Yoksa asaldır.
return true;
}

int main() {
int n = 10'000'000;

int asal_sayisi = 0;
for (int sayi = 1; sayi <= n; sayi++) {
asal_sayisi += asal_mi(sayi);
}

cout << "1'den " << n << "'e kadar " << asal_sayisi << " adet asal sayi var." << "\n";
}[/CODE]
Ideone üzerinden hız testi sonucu (5 saniye): Ideone.com

Maalesef bu yöntem de pek iyi değil çünkü daha iyisi var.

Neymiş o daha iyisi?​

Sieve of Eratosthenes (Eratosten Kalburu) algoritması. Kısaca Sieve diyeceğim çünkü takdir edersiniz ki ismi çok uzun ya.

Hani "1'den n'e kadarki sayıların asallığını kontrol edelim." diye başladık ya, işte Sieve algoritması bu sayıların ardışık olması avantajını kullanıyor, sayılar tek bir grup hâlinde. İsminden de anlaşılabileceği üzere (kalbur/elek) asalları âdeta bir elekten geçiriyor bu algoritma. Merak etmeyin, anlatımı oldukça kısa sürecek.

Şimdi, bir sayı ne zaman asaldır demiştik? Kendisinden küçük ve 1'den büyük bir bölene sahip değilse.
Hadi bunun tersini düşünelim: Bir sayı ne zaman asal değildir? Kendisinden küçük ve 1'den büyük bir bölene sahipse.
Şimdiyse bölen açısından bakalım işe: 1'den büyük bir sayının kendisinden büyük katları kesinlikle asal değildir çünkü katları açısından bu sayı, kendisinden küçük ve 1'den büyüktür. İşte Sieve bunu kullanıyor! Asal olmayanları işaretliyor ki geriye asallar kalsın:

• 2'nin katları 2, 4, 6, 8,... asal değildir.
• 3'ün katları 3, 6, 9, 12,... asal değildir.
• 4'ün katları 4, 8, 12,... asal değildir.
• ...
• 23'ün katları 23, 46, 69,... asal değildir.

Bu şekilde 2'den başlayıp n'e kadar gidip her seferinde sayının katlarını asal değil diye işaretliyoruz. Peki bu çok uzun olmuyor mu, toplamda kaç işlem yapıyoruz?

• 2 için n/2 adet,
• 3 için n/3 adet,
• 4 için n/4 adet,
• ...

Bunların toplamıysa:

n/2 + n/3 + ... + n/n = n * (1/2 + 1/3 + ... + 1/n) = n * ln(n)​

oluyor. Üstelik bir de aslında bunların aşağı yuvarlanmış hallerini alıyoruz tabii, hâliyle biraz daha küçük asıl işlem miktarı. Evet, çok detaya inmeyeyim diye hile yaptım biraz Burada ln(n) oldukça küçük bir sayı diyeyim (e tabanında (doğal) logaritma). Detayları merak ederseniz: Harmonic series (mathematics) - Wikipedia

Öncesinde konuştuğumuz yöntemlere göre çok daha hızlı yani. Hemencecik 10 milyona kadarki sayılar için implementasyonunu göstereyim:

[CODE lang="cpp" title="Sieve algoritması (C++)"]#include <bits/stdc++.h>
using namespace std;

int main() {
int n = 10'000'000; // 1'den n'e kadarki asalları tespit etmek istiyoruz.
vector<bool> asal_mi(n + 1, 1); // Başta tüm sayıları asal varsayıyoruz.
asal_mi[0] = asal_mi[1] = false; // Burasını elle yapıyoruz.

// 2'den n'e kadarki tüm sayıları geziyoruz.
for (int bolen = 2; bolen <= n; bolen++) {
// Katları geziyoruz:
// 2 * bolen, 3 * bolen, 4 * bolen,...
for (int kat = 2 * bolen; kat <= n; kat += bolen) {
asal_mi[kat] = false;
}
}

// Örneğin asalların sayısını bulabiliriz.
int asal_sayisi = 0;
for (int sayi = 1; sayi <= n; sayi++) {
asal_sayisi += asal_mi[sayi];
}

cout << "1'den " << n << "'e kadar " << asal_sayisi << " adet asal sayi var." << "\n";
}[/CODE]

Bir de Ideone üzerinden hız testi sonucunu paylaşayım (0.4 saniye): Ideone.com

Sieve'i hızlandırma​

1. Asal olmayan sayıların katlarını gezmemize gerek yok. Asal olmayan bir sayının katları, kendisinden küçük ve 1'den büyük bir asal böleninin de katlarıdır ve dolayısıyla katlarını çoktan gezmişizdir. Sırf bu gözlemle işlem sayısı n * ln(ln(n))'e iniyor yani bir ln daha geliyor:
   [CODE lang="cpp" title="Hızlandırılmış Sieve"]
   #include <bits/stdc++.h>
   using namespace std;
   
   int main() {
   int n = 10'000'000;
   vector<bool> asal_mi(n + 1, 1);
   asal_mi[0] = asal_mi[1] = false;
   
   for (int bolen = 2; bolen <= n; bolen++) {
   // Sayı asal değilse hiç işlem yapmadan devam edelim.
   if (!asal_mi[bolen])
   continue;
   for (int kat = 2 * bolen; kat <= n; kat += bolen) {
   asal_mi[kat] = false;
   }
   }
   
   int asal_sayisi = 0;
   for (int sayi = 1; sayi <= n; sayi++) {
   asal_sayisi += asal_mi[sayi];
   }
   
   cout << "1'den " << n << "'e kadar " << asal_sayisi << " adet asal sayi var." << "\n";
   }[/CODE]
   Ideone üzerinden hız testi sonucu (0.1 saniye): Ideone.com
2. Katlara sayının karesinden başlama. Çünkü karesinden küçük katlarını çoktan gezmişizdir. k * bolen diye ifade edersek k'nin bir asal böleninin katlarını gezerken k * bolen'e de uğramışızdır. Bu, önceki adımdan daha az hızlandırıyor:
   [CODE lang="cpp" title="İkinci hızlandırma"]
   #include <bits/stdc++.h>
   using namespace std;
   
   int main() {
   int n = 10'000'000;
   vector<bool> asal_mi(n + 1, 1);
   asal_mi[0] = asal_mi[1] = false;
   
   // Burayı da n'in köküne kadar gezecek şekilde ayarlıyoruz çünkü ilerisi için içteki for'a girilmeyecek.
   for (int bolen = 2; bolen * bolen <= n; bolen++) {
   if (!asal_mi[bolen])
   continue;
   for (int kat = bolen * bolen; kat <= n; kat += bolen) {
   asal_mi[kat] = false;
   }
   }
   
   int asal_sayisi = 0;
   for (int sayi = 1; sayi <= n; sayi++) {
   asal_sayisi += asal_mi[sayi];
   }
   
   cout << "1'den " << n << "'e kadar " << asal_sayisi << " adet asal sayi var." << "\n";
   }[/CODE]
   Ideone üzerinden hız testi sonucu (0.05 saniye): Ideone.com

Son optimizasyondan sonra Sieve'in 100 milyona kadarki sayılar için hız testi sonucu (0.76 saniye): Ideone.com
Bayağı hızlı gerçekten.

Ek kaynak​

Daha fazlası için bu değerli kaynağı inceleyebilirsiniz, harika bir anlatım mevcut (İngilizce): Sieve of Eratosthenes - Algorithms for Competitive Programming

Sieve'in modifiye edilmiş birçok versiyonu mevcut. Normalde onlara da değinmeyi düşünüyordum fakat çok uzamasın diye şimdilik değinmemeyi tercih ettim. Umarım işinize yarar Sieve anlatımım. Okuduğunuz için teşekkürler, umarım eğlenmişsinizdir ve...

İyi Sosyal'ler! ​