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).
Algoritma şu şekilde çalışır.
- 2'den n'e kadar bir liste yaratılır. (2,3,4,5,6...n)
- p = 2 yapılarak ilk asal sayı 2 ilan edilir.
- 2p,3p,4p,5p ... gibi katlar alınarak bu sayılar işaretlenir ve asal sayılardan dışlanmış olunur
- 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