Encontrar o n-ésimo número primo

Question

Os seis primeiros números primos são 2,3,5,7,11,13. Qual é
o 10.000º número primo? Discuta a eficiência da sua solução.

Answer 1

A maneira mais imediata (ou seja, a menos sofisticada) é verificar todos os números de 13 em diante para saber se são primos ou não. Cada vez que encontramos um número primo, computamos a sua posição na ordenação dos primos, até chegarmos à posição 10.000º.

Uma melhoria na eficiência desse processo pode ser introduzida a partir do reconhecimento de que números primos maiores que 2 não são pares (na verdade, de 7 em diante terminam sempre com os dígitos 1, 3, 7 ou 9). Assim, a partir daí podemos verificar apenas os números ímpares.

A estratégia consiste em:
1) obter uma função que verifica se um número é primo
2) percorrer uma sequência de números ímpares, testando se são primos
3) incrementar o contador toda vez que um número primo for encontrado
4) parar assim que for obtido o n-ésimo número primo

Uma solução em R seria:

#Função que verifica se um número é primo
primo <- function(p){

  if(sum(p/1:p==p%/%1:p)==2)
    return(1)
  else
    return(0)
}
#Fazemos o contador = 1 e tomamos o primeiro núm. primo, 2.
#Computamos os 5 primeiros números primos, considerando pares e ímpares
count=1
i=2
for(i in 2:11){
  if(primo(i)==1){
    print(c(count,i))
    count=count+1 
  }
  i=i+1
}
#A partir de então, verificamos apenas os números pares
i=i-1
count=count-1
while(count<=10000){
  if(primo(i)==1){
    print(c(count,i,i%%10))
    count=count+1 
  }
  i=i+2
} 

Com isso, encontramos que o 10.000º número primo é 104.729.

Um passo adicional seria pular a verificação dos ímpares terminados em 5. Uma forma de fazer isso seria pular 4 números (ao invés de pular 2) toda vez que o último número verificado terminar em 3. Para isso testamos se o resto da divisão por 10 é igual a 3, como no exemplo abaixo:

while(count<=10000){
  if(tpn(i)==1){
    print(c(count,i,i%%10))
    count=count+1 
  }
  if(i%%10==3){
    k=4
  }
  else{
    k=2
  }
  i=i+k
}

No entanto, cabe ressalvar que testar, a cada passo, a condição de o último dígito ser três introduz perda de eficiência no processo.

Comments

Eu cheguei a testar o código fazendo comparação entre a versão com e sem \begin{equation}i += 4 \end{equation} caso \begin{equation}i % 10 == 3 \end{equation} e o resultado foi inconclusivo.
Pra isso, rodei dois loops com dez iterações cada, cada qual com uma versão do código, pro 100.000º número primo e anotei o tempo médio de execução em cada e comparei. Esse processo foi feito também dez vezes, sendo que em seis a versão com i+=4 se saiu melhor. No entanto, nenhuma diferença foi muito representativa.

---

Olá Henrique!

Muito interessante sua resposta apesar de estar em R (linguagem com a qual não tenho muita familiaridade).

Tentei fazer uma implementação em Python do seu código seguindo a mesma estratégia que você.

def primo(n):
    """
    n: numero natural.
    Retorna True se um numero e primo
    e False caso o contrario.
    """
    if n == 1:
        return False    
    for i in range(2, int(n**(1/2))+1):
        if n%i == 0:
            return False     
    return True


def n_primo(n):
    """
    n: numero natural.
    Encontra o enesimo primo.
    """
    if n == 1:
        return 2
    else:
        counter = 1
        candidate = 1
        
        while counter < n:
            if candidate//10 == 3:
                candidate += 4
            else:
                candidate += 2
            if primo(candidate):
                counter += 1   
    return candidate

if __name__ == "__main__":
    
    print(n_primo(10000))

A diferença é que a primeira função checa se um número é primo dividindo todos os naturais (exceto o 1) até a raiz quadrada daquele número, já que não é preciso checar todos os restos das divisões de um número n por seus antecessores para checar se n é primo (até raiz de n já basta).