Sieve of Eratosthenes
Në shqip: Sita e Eratostenit
ShpjegimiSQ
Sita e Eratostenit gjen të gjithë numrat e thjeshtë deri në N: fillon nga 2 dhe fshin të gjithë shumëfishat e tij, pastaj kalon te numri tjetër i pa fshirë, e kështu me radhë. Ata që mbeten janë të thjeshtë.
EnglishEN
The Sieve of Eratosthenes finds every prime number up to N: start at 2 and cross out all its multiples, then move to the next uncrossed number, and so on. The ones left are prime.
Si ta mendosh
Si sita e miellit: e shkund dhe në fund mbeten vetëm kokrrat që s'kalojnë.
Lexoje në anglisht
Like a flour sieve: shake it and only the grains that don't fall through are left.
Shembull kodipython
def te_thjeshtat(n):
p = [True] * (n + 1); p[0] = p[1] = False
for i in range(2, int(n ** 0.5) + 1):
if p[i]: p[i * i::i] = [False] * len(p[i * i::i])
return [i for i, x in enumerate(p) if x]