fork download
  1. from math import log, floor
  2. import timeit
  3.  
  4. def sieve_of_eratosthene(N):
  5.  
  6. N = floor(N*log(N) + N*(log(log(N))))
  7.  
  8. # Lista de números primos:
  9. numbers = []
  10.  
  11. # Cria-se uma lista referente a todos os inteiros entre 0 e N:
  12. A = [True] * (N+1)
  13.  
  14. # Define os números 0 e 1 como não primos:
  15. A[0] = A[1] = False
  16.  
  17. # Percorra a lista até encontrar o primeiro número primo:
  18. for value, prime in enumerate(A):
  19.  
  20. # O número é primo?
  21. if prime:
  22.  
  23. # Retorna o número primo:
  24. numbers.append(value)
  25.  
  26. # Remova da lista todos os múltiplos do número enontrado:
  27. for i in range(value**2, N+1, value):
  28. A[i] = False
  29.  
  30. return numbers
  31.  
  32. def main():
  33. primes = sieve_of_eratosthene(2e5)
  34. print("Saida:", [primes[i] for i in [7, 1, 199999, 4]])
  35.  
  36. print("Tempo: {}s".format(timeit.timeit(main, number=1)))
Success #stdin #stdout 0.55s 28520KB
stdin
Standard input is empty
stdout
Saida: [19, 3, 2750159, 11]
Tempo: 0.5344637029993464s