import timeit
def sieve_of_eratosthene(N):
# Cria-se uma lista referente a todos os inteiros entre 0 e N:
A = [True] * (N+1)
# Define os números 0 e 1 como não primos:
A[0] = A[1] = False
# Percorra a lista até encontrar o primeiro número primo:
for value, prime in enumerate(A):
# O número é primo?
if prime:
# Retorna o número primo:
yield value
# Remova da lista todos os múltiplos do número enontrado:
for i in range(value**2, N+1, value):
A[i] = False
def main():
primes = list(sieve_of_eratosthene(2750159))
print("Saida:", [primes[i] for i in [7, 1, 199999, 4]])
print("Tempo: {}s".format(timeit.timeit(main, number=1)))
aW1wb3J0IHRpbWVpdAoKZGVmIHNpZXZlX29mX2VyYXRvc3RoZW5lKE4pOgoKICAgICMgQ3JpYS1zZSB1bWEgbGlzdGEgcmVmZXJlbnRlIGEgdG9kb3Mgb3MgaW50ZWlyb3MgZW50cmUgMCBlIE46CiAgICBBID0gW1RydWVdICogKE4rMSkKCiAgICAjIERlZmluZSBvcyBuw7ptZXJvcyAwIGUgMSBjb21vIG7Do28gcHJpbW9zOgogICAgQVswXSA9IEFbMV0gPSBGYWxzZQoKICAgICMgUGVyY29ycmEgYSBsaXN0YSBhdMOpIGVuY29udHJhciBvIHByaW1laXJvIG7Dum1lcm8gcHJpbW86CiAgICBmb3IgdmFsdWUsIHByaW1lIGluIGVudW1lcmF0ZShBKToKCiAgICAgICAgIyBPIG7Dum1lcm8gw6kgcHJpbW8/CiAgICAgICAgaWYgcHJpbWU6CgogICAgICAgICAgICAjIFJldG9ybmEgbyBuw7ptZXJvIHByaW1vOgogICAgICAgICAgICB5aWVsZCB2YWx1ZQoKICAgICAgICAgICAgIyBSZW1vdmEgZGEgbGlzdGEgdG9kb3Mgb3MgbcO6bHRpcGxvcyBkbyBuw7ptZXJvIGVub250cmFkbzoKICAgICAgICAgICAgZm9yIGkgaW4gcmFuZ2UodmFsdWUqKjIsIE4rMSwgdmFsdWUpOgogICAgICAgICAgICAgICAgQVtpXSA9IEZhbHNlCgpkZWYgbWFpbigpOgogICAgcHJpbWVzID0gbGlzdChzaWV2ZV9vZl9lcmF0b3N0aGVuZSgyNzUwMTU5KSkKICAgIHByaW50KCJTYWlkYToiLCBbcHJpbWVzW2ldIGZvciBpIGluIFs3LCAxLCAxOTk5OTksIDRdXSkKCnByaW50KCJUZW1wbzoge31zIi5mb3JtYXQodGltZWl0LnRpbWVpdChtYWluLCBudW1iZXI9MSkpKQo=