Minha contribuição é uma implementação um tanto ingênua. Leva (na minha máquina) aproximadamente 71 segundos para gerar 200.000 primos. Apesar disso, é uma implementação básica, não usa nada de terceiros e é bem fácil de entender.
Note, também, que, nestaNesta implementação, não é necessário saber de antemão qual é o n-ésimo número primo, ou seja, é possível criar uma lista com a qualquerqualquer quantidade de números primos.
Note que não é uma adaptação do seu código, foi criado do zero. O algoritmo consiste em ir procurando de "forma bruta", checando todos os números ímpares.
NoteO algoritmo se baseia na afirmação de que um número é composto (não-primo) se, se somente se, houver algum divisor primo menor ou igual a sua raiz quadrada.
from math import sqrt, ceil
import time
def checkPrime(num):
if num % 2 == 0: return False
i = 3
while i <= ceil(sqrt(num)):
if num % i == 0:
return False
i += 2
return True
def primes(q):
primelist = [2]
number = 3
while len(primelist) < q:
if(checkPrime(number)):
primelist.append(number)
number += 2
return primelist
Versão 2
Este leva 24 segundos (na mesma máquina) pra gerar os 200.000 primos. A diferença deste pro outro é que, na checagem pra saber se um número é primo ou não, são usados apenas os números primos já conhecidos.
Isso porque, como eu disse acima, um número é composto (não-primo) quando tem algum divisor primo menor ou igual a sua raiz quadrada.
def checkPrime(num, baseList):
for p in baseList:
if(p > ceil(sqrt(num))): break
if num % p == 0:
return False
return True
def primes(q):
primelist, number = [2], 3
while len(primelist) < q:
if checkPrime(number, primelist):
primelist.append(number)
number += 2
return primelist
O uso seria assim:
def main():
lista = primes(200000)
print(lista[199999, 1, 7])
Saída: 2750159, 3, 19