Verilen bir n sayısı var ve bu sayıya kadar olan tüm asal sayıların elde edilmesi için sunulmuş en efektif çözümdür (ref: Wiki).

gif

Algoritma şu şekilde çalışır.

  1. 2'den n'e kadar bir liste yaratılır. (2,3,4,5,6...n)
  2. p = 2 yapılarak ilk asal sayı 2 ilan edilir.
  3. 2p,3p,4p,5p ... gibi katlar alınarak bu sayılar işaretlenir ve asal sayılardan dışlanmış olunur
  4. iaşretlenmemiş ilk sayı bulunarak p'ye atanır ve işlemler tekrar edilir.

Çözüm aşağıdaki gibi olur.

def mark(arr, n):
    i = 2
    num = i * n
    while num <= len(arr):
        arr[num - 1] = 1
        i += 1
        num = i * n


def sieve_of_eratosthenes(n):
    if n >= 2:
        arr = [0] * n
        for i in range(1, n):
            if arr[i] == 0:
                print(i + 1)
                mark(arr, i + 1)

if __name__ == '__main__':
    n = 10
    sieve_of_eratosthenes(n)

Agoritmanın anlaşılırlığı için kod uzun tutulmuştur. Çok daha fazla kısaltılması mümkündür.


Comments

comments powered by Disqus