Como gerar 200.000 primos o mais rápido possível em Python?
Para gerar uma grande quantidade de números primos o mais rápido possível em Python, uma opção eficiente é usar o “Crivo de Eratóstenes”, que é um algoritmo clássico para encontrar todos os números primos até um determinado valor.
Aqui está um exemplo de implementação do Crivo de Eratóstenes em Python:
def gerar_primos(n):
is_primo = [True] * (n+1)
is_primo[0] = is_primo[1] = False
for p in range(2, int(n**0.5) + 1):
if is_primo[p]:
for i in range(p*p, n+1, p):
is_primo[i] = False
primos = []
for p in range(2, n+1):
if is_primo[p]:
primos.append(p)
return primos
qtd_primos = 200000
primos = gerar_primos(qtd_primos)
print(primos)
Nesse exemplo, a função gerar_primos
recebe um número n
como parâmetro e retorna uma lista com todos os números primos até n
. O algoritmo usa uma lista booleana is_primo
, onde o valor True
indica que um número é primo e o valor False
indica que ele não é primo.
Primeiramente, todos os valores da lista is_primo
são inicializados como True
, exceto os índices 0 e 1, que são definidos como False
. Em seguida, o algoritmo percorre todos os números de 2 até a raiz quadrada de n
(arredondada para cima), e para cada número p
primo encontrado, marca todos os múltiplos de p
como não primos.
Por fim, os números primos restantes são adicionados à lista primos
e retornados pela função.
No exemplo, a variável qtd_primos
define a quantidade de números primos que serão gerados (nesse caso, 200000). Esses primos são armazenados na variável primos
e são impressos na tela.
É importante mencionar que esse algoritmo é muito eficiente para a geração de uma grande quantidade de números primos. No entanto, a velocidade de execução pode variar dependendo do hardware do computador e da versão do Python utilizada.