Bu yazıda çok temel bir algoritma öğreneceğiz: Eratosthenes'in Eleği.

Problem şu: 10000. asal sayı kaçtır?

Kullanacağımız programlama dili benim gözde dilim: Python.

Kodlamaya yeni başladıysanız temel örnekler için PyBilim'deki Döngülere Örnekler yazısına bakabilirsiniz. Orada, herhangi bir sayının asal olup olmadığını öğrenmek için temel örneği görebilirsiniz. Hemen sözel olarak üstünden geçelim. Sayıyı 2'den sayının kareköküne kadar olan sayılara sırayla böleriz ve kalan olup olmadığına bakarız. Eğer herhangi bir $d$ böleni için kalan 0 ise, sayı $d$'ye tam bölünebiliyordur, yani asal değildir. 2 zaten asal bir sayıdır. Dolayısıyla onu ayrıca kontrol edebiliriz. Herhangi bir $n$ sayısı için yazdığımız döngü en çok 2'den $\sqrt{n}$'ye kadar gidebilir. Yani $\sqrt{n}$'lik oranda bir işlem yaparız. Tek bir $n$ sayısı için bu böyle.

Eğer $i=1,\ldots,n$'yi sağlayan her $i$ sayısı için bunu yapsaydık toplamda yaklaşık $n\sqrt{n}$ oranında işlem yapacaktık. Biraz zaman alacak bir iş. Asal sayı listesi oluşturmak için daha hızlı çalışan bir yöntem var. Şimdi ona bakalım.

Elimizde $n$ tane kutu olsun. Bunları yanyana dizelim. Hepsini eksi ile işaretleyelim. Bu asal değil demek olsun.

| - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - |
  1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20

Şimdi 2'ye bir artı koyalım ve 2'nin katlarını işaretleyelim.

| - | + | - | + | - | + | - | + | - | + | - | + | - | + | - | + | - | + | - | + |
  1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20

2'yi asallar listesine ekleyelim. Listede şu anda sadece 2 var.

Şimdi sıradaki eksiyi bulalım ve onun da tam katlarını artı ile işaretleyelim. Ve Listeye bu sayıyı ekleyelim. Görüldüğü üzere bu sayı 3. 

| - | + | + | + | - | + | - | + | + | + | - | + | - | + | + | + | - | + | - | + |
  1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20

Şu anda listede 2 ve 3 var. Devam edelim. Sıra 5'te.

| - | + | + | + | + | + | - | + | + | + | - | + | - | + | + | + | - | + | - | + |
  1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20

Şimdi sıra 7'de. Sonra sırasıyla 11, 13, 17 ve 19 gelecek. İlk adımda 2'yi işaretlediğimiz için sayıların yarısı işaretlendi. İkinci adımda üçte biri, sonra beşte biri. Tekrarlar var ama çok değil. Bu algoritma $n \log \log n$ oranında.

Şimdi fonksiyona bakalım:

def asallar(limit):
    limitn = limit+1
    asal_degil = [False] * limitn
    asal_listesi = []

    for i in range(2, limitn):
        if asal_degil[i]:
            continue
        for f in xrange(i*2, limitn, i):
            asal_degil[f] = True
        asal_listesi.append(i)

    return asal_listesi

10000. asalın kaç olduğunu bilmiyorum. Limiti elle denedim. 1000000 yetiyor. Haydi 10000. asalı bulalım.

a = asallar(1000000)
print a[9999]
# Sonuç: 104729

1000000 asal sayı bulma için harcanan zaman epey az:

timeit asallar(1000000)
# 1 loops, best of 3: 330 ms per loop

Bu algoritmanın Wikipedia'dan aldığım çok güzel bir animasyonunu da paylaşayım:

Sieve_of_Eratosthenes_animation