from math import log, floor
import timeit
def sieve_of_eratosthene(N):
N = floor(N*log(N) + N*(log(log(N))))
# Lista de números primos:
numbers = []
# 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:
numbers.append(value)
# Remova da lista todos os múltiplos do número enontrado:
for i in range(value**2, N+1, value):
A[i] = False
return numbers
def main():
primes = sieve_of_eratosthene(2e5)
print("Saida:", [primes[i] for i in [7, 1, 199999, 4]])
print("Tempo: {}s".format(timeit.timeit(main, number=1)))
ZnJvbSBtYXRoIGltcG9ydCBsb2csIGZsb29yCmltcG9ydCB0aW1laXQKIApkZWYgc2lldmVfb2ZfZXJhdG9zdGhlbmUoTik6CiAgICAKICAgIE4gPSBmbG9vcihOKmxvZyhOKSArIE4qKGxvZyhsb2coTikpKSkKICAgIAogICAgIyBMaXN0YSBkZSBuw7ptZXJvcyBwcmltb3M6CiAgICBudW1iZXJzID0gW10KIAogICAgIyBDcmlhLXNlIHVtYSBsaXN0YSByZWZlcmVudGUgYSB0b2RvcyBvcyBpbnRlaXJvcyBlbnRyZSAwIGUgTjoKICAgIEEgPSBbVHJ1ZV0gKiAoTisxKQogCiAgICAjIERlZmluZSBvcyBuw7ptZXJvcyAwIGUgMSBjb21vIG7Do28gcHJpbW9zOgogICAgQVswXSA9IEFbMV0gPSBGYWxzZQogCiAgICAjIFBlcmNvcnJhIGEgbGlzdGEgYXTDqSBlbmNvbnRyYXIgbyBwcmltZWlybyBuw7ptZXJvIHByaW1vOgogICAgZm9yIHZhbHVlLCBwcmltZSBpbiBlbnVtZXJhdGUoQSk6CiAKICAgICAgICAjIE8gbsO6bWVybyDDqSBwcmltbz8KICAgICAgICBpZiBwcmltZToKIAogICAgICAgICAgICAjIFJldG9ybmEgbyBuw7ptZXJvIHByaW1vOgogICAgICAgICAgICBudW1iZXJzLmFwcGVuZCh2YWx1ZSkKIAogICAgICAgICAgICAjIFJlbW92YSBkYSBsaXN0YSB0b2RvcyBvcyBtw7psdGlwbG9zIGRvIG7Dum1lcm8gZW5vbnRyYWRvOgogICAgICAgICAgICBmb3IgaSBpbiByYW5nZSh2YWx1ZSoqMiwgTisxLCB2YWx1ZSk6CiAgICAgICAgICAgICAgICBBW2ldID0gRmFsc2UKICAgICAgICAgICAgICAgIAogICAgcmV0dXJuIG51bWJlcnMKIApkZWYgbWFpbigpOgogICAgcHJpbWVzID0gc2lldmVfb2ZfZXJhdG9zdGhlbmUoMmU1KQogICAgcHJpbnQoIlNhaWRhOiIsIFtwcmltZXNbaV0gZm9yIGkgaW4gWzcsIDEsIDE5OTk5OSwgNF1dKQogCnByaW50KCJUZW1wbzoge31zIi5mb3JtYXQodGltZWl0LnRpbWVpdChtYWluLCBudW1iZXI9MSkpKQ==