Com o próprio Crivo de Eratóstenes eu consegui resultados bem satisfatórios. Vale lembrar que, como o crivo retorna a lista de todos os números primos menores que o valor de entrada, teremos que informar o maior valor primo que o programa aceitará. O enunciado fala que é garantido que não será solicitado um número após o 200.000°, então inicialmente devemos conhecer qual é este valor: 2.750.159.
Uma implementação bastante simples do crivo é:
def sieve_of_eratosthene(N):
# 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:
yield value
# Remova da lista todos os múltiplos do número encontrado:
for i in range(value**2, N+1, value):
A[i] = False
Assim, podemos obter todos os 200.000 primeiros números primos fazendo:
primes = list(sieve_of_eratosthene(2750159))
E gerar a saída da seguinte forma:
print("Saída:", [primes[i] for i in [7, 1, 199999, 4]]) # Saída: [19, 3, 2750159, 11]
Sendo [7, 1, 199999, 4]
a entrada do programa.
Nota: o 199.999° número primo será 2.750.131, como esperado, apenas se o número 2 ocupar o índice 1. Considerando que a implementação define o índice 0 para o valor 2, o valor esperado na saída seria referente ao índice 199.998°.
Utilizando o módulo timeit
para a medição do tempo, obtive um tempo médio, em 100 execuções, de 0.69539769177063s
.
Veja funcionando no Ideone.
Uma breve explicação do código
A primeira linha da função, A = [True] * (N+1)
cria uma lista de N+1
elementos, todos definidos como True
, indicando inicialmente que todos os valores entre 0 e N são números primos. Logo após, é definido os valores 0 e 1 como False
, indicando que estes não são números primos. E com um laço de repetição, é percorrido todos os outros valores e sempre que achar um valor primo, retorne-o e elimina da lista, definindo como False
, todos os números que são múltiplos desse primo encontrado. Para uma melhor visualização, a lista A
seria algo como:
A = [False, False, True, True, False, True, False, ...]
Indicando que 0 não é primo, 1 não é primo, 2 é primo, 3 é primo, 4 não é primo, 5 é primo, 6 não é primo, assim sucessivamente. O que a função enumerate
faz é retornar um par de valores onde o primeiro representa o índice na lista e o segundo o valor propriamente dito. Assim, fazendo enumerate(A)
, seria retornado algo semelhante à:
[(0, False), (1, False), (2, True), (3, True), (4, False), (5, True), (6, False), ...]
E é por isso que no for
existem dois valores. O primeiro valor retornado de enumerate
é atribuído à value
e o segundo à prime
, assim, quando prime
for verdadeiro, sabemos que value
será um número primo.
for value, prime in enumerate(A):
...
Já o yield
faz o papel do return
, porém, para um gerador. Confesso que eu acabei complicando mais que o necessário neste código utilizando um gerador, pois visto que o gerador deverá ser convertido para uma lista, eu poderia gerá-la diretamente. O código ficaria assim:
def sieve_of_eratosthene(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
Veja funcionando no Ideone.
Perceba que a principal diferença é que onde antes eu utilizada o yield
, agora utilizei o append
de uma lista.
Uma implementação extra
Assim como comentado pelo LINQ em sua resposta, o fato de ter que conhecer de antemão o n-ésimo valor primo pode ser considerado um limitante da solução. Uma alternativa prática é aplicar o conceito matemático apresentado no final desta resposta para calcular um valor primo próximo ao desejado. Sabendo que o n-ésimo número primo, Pn, é menor que n ln(n) + n ln(ln(n))
, se calcularmos todos os valores primos até este valor temos certeza que teremos calculado o valor de Pn. Algo como:
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 encontrado:
for i in range(value**2, N+1, value):
A[i] = False
return numbers
Veja funcionando no Ideone.
Apenas com a adição da primeira linha, agora podemos chamar a função sieve_of_eratosthene(2e5)
para obter os 200.000 primeiros números primos. Na verdade, obtém-se até mais, por isso o tempo de execução pode aumentar.
Possível alternativa
É provado matematicamente, se entendi bem, que o n-ésimo número primo, sendo n maior ou igual a 6, pertencerá ao conjunto de números definido por:
Por exemplo, para n = 199999
, é obtido o seguinte conjunto:
2741586 < P_n < 2941585
Que contém o valor esperado 2750159; porém, este não será o único número primo neste intervalo, então o desafio seguindo esta lógica seria identificar corretamente o valor dentro do intervalo.