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