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.