Calculando e imprimindo o número primo

Eu estou tentando calcular números primos, o que eu já fiz. Mas eu quero calcular e imprimir APENAS o n-ésimo número primo (input do usuário), enquanto calculo o resto (eles não serão impressos) apenas o n-ésimo número primo será impresso.

Aqui está o que eu escrevi até agora:

import java.util.Scanner; /** * Calculates the nth prime number * @author {Zyst} */ public class Prime { public static void main(String[] args) { Scanner input = new Scanner(System.in); int n, i = 2, x = 2; System.out.printf("This program calculates the nth Prime number\n"); System.out.printf("Please enter the nth prime number you want to find: "); n = input.nextInt(); for(i = 2, x = 2; i <= n; i++) { for(x = 2; x < i; x++) { if(i % x == 0) { break; } } if(x == i) { System.out.printf("\n%d is prime", x); } } } } 

Este é o programa que escrevi para calcular os números primos de 1 a n. No entanto, quero apenas imprimir o enésimo número primo,

O que eu pensei em fazer é fazer algum tipo de contagem int e ++ cada vez que encontrar um primo, e quando a contagem == n, em seguida, ele imprime esse número, mas eu não consigo descobrir como aterrá-lo.

    Para calcular o n-ésimo primo, conheço duas variantes principais.

    O caminho direto

    Isso é contar todos os primos a partir de 2, à medida que você os encontra, até atingir o número desejado.

    Isso pode ser feito com diferentes níveis de sofisticação e eficiência, e há duas maneiras conceitualmente diferentes de fazê-lo. O primeiro é

    Testando a primalidade de todos os números em sequência

    Isso seria realizado por uma function de motorista como

     public static int nthPrime(int n) { int candidate, count; for(candidate = 2, count = 0; count < n; ++candidate) { if (isPrime(candidate)) { ++count; } } // The candidate has been incremented once after the count reached n return candidate-1; } 

    e a parte interessante que determina a eficiência é a function isPrime .

    O caminho óbvio para um teste de primalidade, dada a definição de um primo como um número maior do que 1, que é divisível apenas por 1 e, por si só, que aprendemos na escola¹, é

    Divisão experimental

    A tradução direta da definição em código é

     private static boolean isPrime(int n) { for(int i = 2; i < n; ++i) { if (n % i == 0) { // We are naive, but not stupid, if // the number has a divisor other // than 1 or itself, we return immediately. return false; } } return true; } 

    mas, como você logo descobrirá se tentar, sua simplicidade é acompanhada de lentidão. Com esse teste de primalidade, você pode encontrar o milésimo primo, 7919, em poucos milissegundos (cerca de 20 no meu computador), mas encontrar o 10 mil primo, 104729, leva segundos (~ 2,4s), o 100000 th primo, 1299709 , vários minutos (cerca de 5), o milionésimo primo, 15485863, levaria cerca de oito horas e meia, o décimo milionésimo primo, 179424673, semanas e assim por diante. A complexidade do tempo de execução é pior que a quadrática - Θ (n² * log n).

    Então, gostaríamos de acelerar um pouco o teste da primalidade. Um passo que muitas pessoas tomam é a percepção de que um divisor de n (diferente de n si) pode ser no máximo n/2 . Se usarmos esse fato e deixarmos que o loop de divisão de avaliação só seja executado com n/2 vez de n-1 , como o tempo de execução do algoritmo muda? Para números compostos, o limite inferior do loop não altera nada. Para primos, o número de divisões experimentais é reduzido pela metade, então, em geral, o tempo de execução deve ser reduzido por um fator um pouco menor que 2. Se você experimentar, verá que o tempo de execução é quase exatamente a metade, então O tempo é gasto verificando a primalidade dos primos, apesar de haver muito mais compostos do que primos.

    Agora, isso não ajudou muito se quisermos encontrar o centésimo milionésimo primeiro, então temos que fazer melhor. Tentando reduzir ainda mais o limite do loop, vamos ver para quais números o limite superior de n/2 é realmente necessário. Se n/2 é um divisor de n , então n/2 é um inteiro, em outras palavras, n é divisível por 2. Mas então o laço não passa de 2, então nunca (exceto n = 4 ) atinge n/2 . Muito bom, então qual é o segundo maior divisor possível de n ? Por que, n/3 claro. Mas n/3 só pode ser um divisor de n se for um inteiro, em outras palavras, se n é divisível por 3. Então o laço sairá em 3 (ou antes, em 2) e nunca alcançará n/3 (exceto para n = 9 ). O segundo maior divisor possível ...

    Aguarde um minuto! Nós temos 2 < -> n/2 e 3 < -> n/3 . Os divisores de n vêm em pares.

    Se considerarmos o par (d, n/d) dos divisores correspondentes de n , ou d = n/d , isto é, d = √n , ou um deles, digamos d , é menor que o outro. Mas então d*d < d*(n/d) = n e d < √n d*d < d*(n/d) = n . Cada par de divisores correspondentes de n contém (pelo menos) um que não excede √n .

    Se n é composto, seu menor divisor não trivial não excede √n .

    Assim, podemos reduzir o limite do loop para √n e isso reduz a complexidade do tempo de execução do algoritmo. Agora deve ser Θ (n 1.5 * √ (log n)), mas empiricamente parece escalar um pouco melhor - no entanto, não há dados suficientes para tirar conclusões confiáveis ​​dos resultados empíricos.

    Que encontra o milionésimo primo em cerca de 16 segundos, o décimo milionésimo em menos de nove minutos, e encontraria o milionésimo milionésimo em quatro horas e meia. Isso ainda é lento, mas muito longe dos dez anos ou mais levaria a divisão de julgamento ingênua.

    Como existem quadrados de primos e produtos de dois primos próximos, como 323 = 17 * 19, não podemos reduzir o limite para o loop de divisão de teste abaixo de √n . Portanto, enquanto permanecer com a divisão experimental, devemos procurar outras maneiras de melhorar o algoritmo agora.

    Uma coisa fácil de ver é que nenhum primo além de dois é par, então precisamos apenas checar os números ímpares depois de termos resolvido o 2. Mas isso não faz muita diferença, já que os números pares são os mais baratos de se encontrar. composto - e a maior parte do tempo ainda é gasto verificando a primalidade dos primos. Entretanto, se olharmos os números pares como divisores candidatos, veremos que se n é divisível por um número par, n ele mesmo deve ser par, então (exceto 2) ele terá sido reconhecido como composto antes da divisão por qualquer número par maior do que 2 é tentado. Portanto, todas as divisões por números pares maiores que 2 que ocorrem no algoritmo devem necessariamente deixar um resto diferente de zero. Podemos, portanto, omitir essas divisões e verificar a divisibilidade apenas por 2 e os números ímpares de 3 a √n . Isso significa (não exatamente) o número de divisões necessárias para determinar um número como primo ou composto e, portanto, o tempo de execução. Isso é um bom começo, mas podemos fazer melhor?

    Outra grande família de números são os múltiplos de 3. Cada terceira divisão que realizamos é por um múltiplo de 3, mas se n é divisível por um deles, também é divisível por 3 e, portanto, nenhuma divisão por 9, 15, 21 ... que nós executamos em nosso algoritmo jamais deixaremos um resto de 0. Então, como podemos pular essas divisões? Bem, os números divisíveis por nem 2 nem 3 são precisamente os números da forma 6*k ± 1 . A partir de 5 (já que estamos interessados ​​apenas em números maiores que 1), eles são 5, 7, 11, 13, 17, 19, ..., o passo de um para o próximo alterna entre 2 e 4, que é bastante fácil, para que possamos usar

     private static boolean isPrime(int n) { if (n % 2 == 0) return n == 2; if (n % 3 == 0) return n == 3; int step = 4, m = (int)Math.sqrt(n) + 1; for(int i = 5; i < m; step = 6-step, i += step) { if (n % i == 0) { return false; } } return true; } 

    Isso nos dá outra aceleração por um fator de (quase) 1,5, então precisamos de cerca de uma hora e meia para o centésimo milionésimo primo.

    Se continuarmos esta rota, o próximo passo é a eliminação de múltiplos de 5. Os números coprime para 2, 3 e 5 são os números da forma

     30*k + 1, 30*k + 7, 30*k + 11, 30*k + 13, 30*k + 17, 30*k + 19, 30*k + 23, 30*k + 29 

    então, precisaríamos apenas dividir por oito de cada trinta números (mais os três menores primos). Os passos de um para o outro, a partir de 7, mudam para 4, 2, 4, 2, 4, 6, 2, 6. Isso ainda é fácil de implementar e produz outro aumento de velocidade por um fator de 1,25 (menos um pouco para código mais complicado). Indo mais longe, os múltiplos de 7 seriam eliminados, deixando 48 de cada 210 números para dividir por, então 11 (480/2310), 13 (5760/30030) e assim por diante. Cada primo p cujos múltiplos são eliminados produz um aumento de velocidade (quase) p/(p-1) , então o retorno diminui enquanto o custo (complexidade de código, espaço para a tabela de consulta para as etapas) aumenta com cada primo.

    Em geral, um pararia em breve, depois de eliminar os múltiplos de talvez seis ou sete primos (ou até menos). Aqui, no entanto, podemos seguir até o fim, quando os múltiplos de todos os primos foram eliminados e apenas os primos são deixados como divisores candidatos. Como estamos encontrando todos os primos em ordem, cada primo é encontrado antes de ser necessário como um divisor de candidato e pode ser armazenado para uso futuro. Isso reduz a complexidade algorítmica para - se não calculei mal - O (n 1.5 / √ (log n)). Ao custo do uso do espaço para armazenar os primos.

    Com a divisão de avaliação, isso é tão bom quanto possível, você tem que tentar dividir por todos os primos para √n ou pela primeira divisão n para determinar a primalidade de n . Que encontra o centésimo milionésimo primo em cerca de meia hora aqui.

    Então, e quanto a

    Testes rápidos de primalidade

    Os primos têm outras propriedades teóricas numéricas do que a ausência de divisores não triviais que os números compostos geralmente não têm. Tais propriedades, se forem rápidas de verificar, podem formar a base de testes probabilísticos ou determinísticos de primalidade. A arquetípica propriedade deste tipo está associada ao nome de Pierre de Fermat, que, no início do século XVII , descobriu que

    Se p é um primo, então p é um divisor de (a p-a ) para todos os a .

    Isto - o chamado "pequeno teorema" de Fermat - é, na formulação equivalente

    Seja p um primo e a não divisível por p . Então p divide um p-1 - 1.

    a base da maioria dos testes de primalidade rápida difundidos (por exemplo Miller-Rabin) e variantes ou análogos disso aparecem ainda mais (por exemplo, Lucas-Selfridge).

    Então, se quisermos saber se um número ímpar n pequeno demais é um primo (números pares e pequenos são eficientemente tratados por divisão de teste), podemos escolher qualquer número a (> 1) que não seja um múltiplo de n , por exemplo 2, e verifique se n divide um n-1 - 1. Como um n-1 se torna enorme, isso é feito de maneira mais eficiente verificando se a^(n-1) ≡ 1 (mod n) , ie por exponenciação modular. Se essa congruência não é válida, sabemos que n é composto. Se isso acontece, no entanto, não podemos concluir que n é primo, por exemplo 2^340 ≡ 1 (mod 341) , mas 341 = 11 * 31 é composto. Números compostos n tais que a^(n-1) ≡ 1 (mod n) são chamados de pseudoprimes de Fermat para a base a .

    Mas tais ocorrências são raras. Dada qualquer base a > 1 , embora haja um número infinito de pseudoprimes de Fermat para basear a , eles são muito mais raros que os primos reais. Por exemplo, existem apenas 78 pseudoprimes Fermat base 2 e pseudoprimes 76 Fermat 76 base 3 abaixo de 100000, mas 9592 primos. Então, se alguém escolhe um odd arbitrário n > 1 e uma base arbitrária a > 1 e encontra a^(n-1) ≡ 1 (mod n) , há uma boa chance de que n seja realmente primo.

    No entanto, estamos em uma situação ligeiramente diferente, nos é dado n e só podemos escolher a . Então, para um n composto ímpar, para quantos, 1 < a < n-1 pode a^(n-1) ≡ 1 (mod n) retido? Infelizmente, existem números compostos - números Carmichael - de tal forma que a congruência vale para cada coprime a n . Isso significa que para identificar um número de Carmichael como composto com o teste de Fermat, temos que escolher uma base que seja um múltiplo de um dos principais divisores de n - pode não haver muitos desses múltiplos.

    Mas podemos fortalecer o teste de Fermat para que os compostos sejam detectados de forma mais confiável. Se p for um primo ímpar, escreva p-1 = 2*m . Então, se 0 < a < p ,

     a^(p-1) - 1 = (a^m + 1) * (a^m - 1) 

    p divide exatamente um dos dois fatores (os dois fatores diferem em 2, então seu maior divisor comum é 1 ou 2). Se m é par, podemos dividir a^m - 1 da mesma maneira. Continuando, se p-1 = 2^s * k com k ímpar, escreva

     a^(p-1) - 1 = (a^(2^(s-1)*k) + 1) * (a^(2^(s-2)*k) + 1) * ... * (a^k + 1) * (a^k - 1) 

    então p divide exatamente um dos fatores. Isto dá origem ao forte teste de Fermat,

    Seja n > 2 um número ímpar. Escreva n-1 = 2^s * k com k ímpar. Dado qualquer a com 1 < a < n-1 , se

    1. a^k ≡ 1 (mod n) ou
    2. a^((2^j)*k) ≡ -1 (mod n) para qualquer j com 0 < = j < s

    então n é um primo provável forte (Fermat) para a base a . Uma base forte composta a primo provável (Fermat) é chamado de pseudoprimo forte (Fermat) para a base a . Pseudoprimes fortes de Fermat são ainda mais raras do que as pseudoprimes comuns de Fermat, abaixo de 1000000, existem 78498 primos, 245 base-2 Fermat pseudoprimes e apenas 46 base-2 Fermat pseudoprimes fortes. Mais importante, para qualquer compósito ímpar n , há no máximo (n-9)/4 bases 1 < a < n-1 para as quais n é um forte Fermat pseudoprimo.

    Portanto, se n é um composto ímpar, a probabilidade de que n passe de k testes fortes de Fermat com bases escolhidas aleatoriamente entre 1 e n-1 (limites exclusivos) é menor que 1/4^k .

    Um teste forte de Fermat leva os passos O (log n), cada passo envolve uma ou duas multiplicações de números com O (log n) bits, então a complexidade é O ((log n) ^ 3) com multiplicação ingênua [para grande n algoritmos de multiplicação mais sofisticados podem valer a pena].

    O teste de Miller-Rabin é o teste de Fermat forte em dobra-k com bases escolhidas aleatoriamente. É um teste probabilístico, mas para limites pequenos o suficiente, são conhecidas combinações curtas de bases que dão um resultado determinístico.

    Testes fortes de Fermat fazem parte do teste determinista da APRCL.

    É aconselhável preceder tais testes com divisão de tentativas pelos primeiros primos pequenos, uma vez que as divisões são comparativamente baratas e eliminam a maioria dos compósitos.

    Para o problema de encontrar o enésimo primo, na faixa em que testar todos os números de primalidade é viável, existem combinações conhecidas de bases que tornam o teste forte de Fermat múltiplo correto, de modo que daria um mais rápido - O (n * n) 4 ) - algoritmo.

    Para n < 2^32 , as bases 2, 7 e 61 são suficientes para verificar a primalidade. Usando isso, o centésimo milionésimo primo é encontrado em cerca de seis minutos.

    Eliminando compósitos por divisores principais, a peneira de Eratóstenes

    Em vez de investigar os números em sequência e verificar se cada um é primo a partir do zero, pode-se também considerar todo o conjunto de números relevantes como uma única peça e eliminar os múltiplos de um dado primo de uma só vez. Isto é conhecido como a peneira de Eratóstenes:

    Para encontrar os números primos não excedendo N

    1. faça uma lista de todos os números de 2 a N
    2. para cada k de 2 a N : se k ainda não foi cruzado, é primo; cross off todos os múltiplos de k como compósitos

    Os primos são os números da lista que não são cruzados.

    Este algoritmo é fundamentalmente diferente da divisão experimental, embora ambos utilizem diretamente a caracterização de divisibilidade de primos, em contraste com o teste de Fermat e testes similares que usam outras propriedades de primos.

    Na divisão experimental, cada número n é emparelhado com todos os primos não excedendo o menor de √n e o menor divisor primo de n . Como a maioria dos compósitos tem um divisor primário muito pequeno, a detecção de compósitos é barata aqui, em média. Mas o teste de primos é caro, uma vez que existem relativamente poucos primos abaixo de √n . Embora haja muito mais compostos do que primos, o custo do teste de primos é tão alto que ele domina completamente o tempo total de execução e torna a divisão de teste um algoritmo relativamente lento. A divisão de teste para todos os números menores que N leva os passos O (N 1.5 / (log N) ²).

    Na peneira, cada composto n está emparelhado com todos os seus principais divisores, mas apenas com aqueles. Assim, os números primos são os números mais baratos, eles só são vistos de uma vez, enquanto os compostos são mais caros, são cruzados várias vezes. Pode-se acreditar que, uma vez que uma peneira contém muito mais números "caros" do que "baratos", em geral seria um algoritmo ruim. No entanto, um número composto não tem muitos divisores principais distintos - o número de divisores principais distintos de n é limitado por log n , mas normalmente é muito menor, a média do número de divisores principais distintos dos números < = n é log log n - assim, mesmo os números "caros" da peneira não são, em média, mais caros (ou dificilmente mais) do que os números "baratos" da divisão experimental.

    Peneirando até N , para cada primo p , há múltiplos Θ(N/p) para o cross off, então o número total de cross-off é Θ(∑ (N/p)) = Θ(N * log (log N)) . Isso produz algoritmos muito mais rápidos para encontrar os primos até N que a divisão de teste ou testes sequenciais com os testes mais rápidos de primalidade.

    Há, no entanto, uma desvantagem para a peneira, ele usa a memory O(N) . (Mas com uma peneira segmentada, isso pode ser reduzido a O(√N) sem aumentar a complexidade do tempo.)

    Para encontrar o enésimo primo, em vez dos primos até N , existe também o problema de que não se sabe de antemão até que ponto a peneira deve chegar.

    Este último pode ser resolvido usando o teorema do número primo. O PNT diz

     π(x) ~ x/log x (equivalently: lim π(x)*log x/x = 1), 

    onde π(x) é o número de primos que não excedem x (aqui e abaixo, log deve ser o logaritmo natural, para as complexidades algorítmicas não é importante qual base é escolhida para os logaritmos). A partir disso, segue-se que p(n) ~ n*log n , onde p(n) é o enésimo primo, e há bons limites superiores para p(n) conhecidos a partir de análises mais profundas, em particular

     n*(log n + log (log n) - 1) < p(n) < n*(log n + log (log n)), for n >= 6. 

    Então, pode-se usar isso como limite de peneiramento, não excede o alvo.

    O requisito de espaço O(N) pode ser superado usando uma peneira segmentada. Pode-se então gravar os primos abaixo de √N para o consumo de memory O(√N / log N) e usar segmentos de comprimento crescente (O (√N) quando a peneira estiver próxima de N).

    Existem algumas melhorias fáceis no algoritmo, conforme indicado acima:

    1. comece cruzando múltiplos de p somente em , não em 2*p
    2. elimine os números pares da peneira
    3. eliminar os múltiplos de mais pequenos primos da peneira

    Nenhuma delas reduz a complexidade algorítmica, mas todas reduzem os fatores constantes em uma quantidade significativa (como na divisão experimental, a eliminação de múltiplos de p produz menos aceleração para p maior, enquanto aumenta a complexidade do código mais do que para p menor).

    Usando as duas primeiras melhorias, o rendimento

     // Entry k in the array represents the number 2*k+3, so we have to do // a bit of arithmetic to get the indices right. public static int nthPrime(int n) { if (n < 2) return 2; if (n == 2) return 3; int limit, root, count = 1; limit = (int)(n*(Math.log(n) + Math.log(Math.log(n)))) + 3; root = (int)Math.sqrt(limit) + 1; limit = (limit-1)/2; root = root/2 - 1; boolean[] sieve = new boolean[limit]; for(int i = 0; i < root; ++i) { if (!sieve[i]) { ++count; for(int j = 2*i*(i+3)+3, p = 2*i+3; j < limit; j += p) { sieve[j] = true; } } } int p; for(p = root; count < n; ++p) { if (!sieve[p]) { ++count; } } return 2*p+1; } 

    que encontra o centésimo milionésimo primo, 2038074743, em cerca de 18 segundos. Esse tempo pode ser reduzido para cerca de 15 segundos (aqui, YMMV) armazenando os sinalizadores compactados, um bit por flag, em vez de como boolean s, já que o uso reduzido de memory fornece uma melhor localidade de cache.

    Embalando as bandeiras, eliminando também múltiplos de 3 e usando bit-twiddling para contagem rápida e mais rápida,

     // Count number of set bits in an int public static int popCount(int n) { n -= (n >>> 1) & 0x55555555; n = ((n >>> 2) & 0x33333333) + (n & 0x33333333); n = ((n >> 4) & 0x0F0F0F0F) + (n & 0x0F0F0F0F); return (n * 0x01010101) >> 24; } // Speed up counting by counting the primes per // array slot and not individually. This yields // another factor of about 1.24 or so. public static int nthPrime(int n) { if (n < 2) return 2; if (n == 2) return 3; if (n == 3) return 5; int limit, root, count = 2; limit = (int)(n*(Math.log(n) + Math.log(Math.log(n)))) + 3; root = (int)Math.sqrt(limit); switch(limit%6) { case 0: limit = 2*(limit/6) - 1; break; case 5: limit = 2*(limit/6) + 1; break; default: limit = 2*(limit/6); } switch(root%6) { case 0: root = 2*(root/6) - 1; break; case 5: root = 2*(root/6) + 1; break; default: root = 2*(root/6); } int dim = (limit+31) >> 5; int[] sieve = new int[dim]; for(int i = 0; i < root; ++i) { if ((sieve[i >> 5] & (1 < < (i&31))) == 0) { int start, s1, s2; if ((i & 1) == 1) { start = i*(3*i+8)+4; s1 = 4*i+5; s2 = 2*i+3; } else { start = i*(3*i+10)+7; s1 = 2*i+3; s2 = 4*i+7; } for(int j = start; j < limit; j += s2) { sieve[j >> 5] |= 1 < < (j&31); j += s1; if (j >= limit) break; sieve[j >> 5] |= 1 < < (j&31); } } } int i; for(i = 0; count < n; ++i) { count += popCount(~sieve[i]); } --i; int mask = ~sieve[i]; int p; for(p = 31; count >= n; --p) { count -= (mask >> p) & 1; } return 3*(p+(i< <5))+7+(p&1); } 

    encontra o centésimo milionésimo primo em cerca de 9 segundos, o que não é insuportavelmente longo.

    Existem outros tipos de peneiras primárias, de particular interesse é a peneira de Atkin, que explora o fato de que certas classs de congruência de primos (racionais) são compostas no anel de inteiros algébricos de algumas extensões quadráticas de ℚ. Aqui não é o lugar para expandir a teoria matemática, basta dizer que a peneira de Atkin tem complexidade algorítmica menor do que a peneira de Eratóstenes e, portanto, é preferível para grandes limites (para limites pequenos, uma peneira Atkin não excessivamente otimizada tem maior sobrecarga e, portanto, pode ser mais lento do que uma peneira Eratóstenes comparativamente otimizada). A biblioteca primegen de DJ Bernstein (escrita em C) está bem otimizada para números abaixo de 2 32 e encontra o centésimo milionésimo primo (aqui) em cerca de 1,1 segundo.

    O caminho mais rápido

    Se quisermos apenas encontrar o enésimo primo, não há valor intrínseco em encontrar todos os primos menores. Se podemos pular a maioria deles, podemos economizar muito tempo e trabalho. Dada uma boa aproximação a(n) ao enésimo primo p(n) , se tivermos uma maneira rápida de calcular o número de primos π(a(n)) não excedendo a(n) , podemos então peneirar um pequeno faixa acima ou abaixo de a(n) para identificar os poucos primos ausentes ou em excesso entre a(n) e p(n) .

    Nós vimos uma aproximação razoavelmente boa e facilmente computada para p(n) acima, nós poderíamos

     a(n) = n*(log n + log (log n)) 

    por exemplo.

    Um bom método para calcular π(x) é o método de Meissel-Lehmer , que calcula π(x) em aproximadamente O(x^0.7) tempo (a complexidade exata depende da implementação, um refinamento por Lagarias, Miller, Odlyzko, Deléglise e Rivat permite calcular um π(x) no tempo O (x 2/3 / log² x)).

    Começando com a aproximação simples a(n) , calculamos e(n) = π(a(n)) - n . Pelo teorema do número primo, a densidade de primos próximos a(n) é de cerca de 1/log a(n) , então esperamos que p(n) esteja próximo de b(n) = a(n) - log a(n)*e(n) e nós vamos peneirar um intervalo um pouco maior que o log a(n)*e(n) . Para maior confiança de que p(n) está no intervalo peneirado, pode-se aumentar o intervalo por um fator de 2, digamos, que quase certamente será grande o suficiente. Se o intervalo parece muito grande, pode-se iterar com a melhor aproximação b(n) no lugar de a(n) , computar π(b(n)) e f(n) = π((b(n)) - n Tipicamente, |f(n)| será muito menor que |e(n)| Se f(n) for aproximadamente -e(n) , c(n) = (a(n) + b(n)) / 2 será uma melhor aproximação para p(n) Apenas no caso muito improvável de que f(n) é muito próximo de e(n) (e não muito próximo de 0), encontrando uma aproximação suficientemente boa para p(n) que o estágio final de peneiramento pode ser feito em tempo comparável à computação π(a(n)) se torna um problema.

    Em geral, após uma ou duas melhorias na aproximação inicial, o intervalo a ser peneirado é pequeno o suficiente para que o estágio de peneiramento tenha uma complexidade de O (n ^ 0,75) ou melhor.

    Este método encontra o centésimo milionésimo primo em cerca de 40 milésimos de segundo, e o décimo segundo, 29996224275833, em menos de oito segundos.


    tl: dr: Encontrar o n th prime pode ser feito eficientemente, mas quanto mais eficiente você quiser, mais matemática estará envolvida.


    Eu tenho código Java para a maioria dos algoritmos discutidos aqui , no caso de alguém querer brincar com eles.


    ¹ Além da observação de almas superinteressadas: A definição de primos usados ​​na matemática moderna é diferente, aplicável em situações muito mais gerais. Se nós adaptamos a definição da escola para include números negativos - então um número é primo se não é nem 1 nem -1 e divisível somente por 1, -1, ele próprio e seu negativo - isso define (para inteiros) o que é hoje chamado de elemento irredutível de ℤ, no entanto, para inteiros, as definições de elementos primos e irredutíveis coincidem.

     int counter = 0; for(int i = 1; ; i++) { if(isPrime(i) counter++; if(counter == userInput) { print(i); break; } } 

    Edit: Sua function principal poderia usar um pouco de trabalho. Aqui está uma que eu escrevi:

     private static boolean isPrime(long n) { if(n < 2) return false; for (long i = 2; i * i <= n; i++) { if (n % i == 0) return false; } return true; } 

    Nota - você só precisa subir para o sqrt (n) ao olhar para fatores, daí o i * i < = n

    Você está tentando fazer muito no método principal. Você precisa dividir isso em partes mais gerenciáveis. Escreva um método boolean isPrime(int n) que retorna true se um número for primo e false caso contrário. Em seguida, modifique o método principal para usar o isPrime.

    java.math.BigInteger tem um método nextProbablePrime (). Embora eu esteja supondo que isso é destinado a criptografia, você poderia usá-lo para o seu trabalho.

     BigInteger prime = BigInteger.valueOf(0); for (int i = 0; i < n; i++) { prime = prime.nextProbablePrime(); } System.out.println(prime.intValue()); 

    Acabei de adicionar as linhas que faltam em seu próprio processo de pensamento.

    static int nthPrimeFinder (int n) {

      int counter = 1; // For 1 and 2. assuming n is not 1 or 2. int i = 2; int x = 2; int tempLength = n; while (counter < = n) { for (; i <= tempLength; i++) { for (x = 2; x < i; x++) { if (i % x == 0) { break; } } if (x == i && counter < n) { //System.out.printf("\n%d is prime", x); counter++; if (counter == n) { System.out.printf("\n%d is prime", x); return counter; } } } tempLength = tempLength+n; } return 0; } 
     public class prime{ public static void main(String ar[]) { int count; int no=0; for(int i=0;i<1000;i++){ count=0; for(int j=1;j< =i;j++){ if(i%j==0){ count++; } } if(count==2){ no++; if(no==Integer.parseInt(ar[0])){ System.out.println(no+"\t"+i+"\t") ; } } } } } 

    Eu posso ver que você recebeu muitas respostas corretas e muito detalhadas. Eu acredito que você não está testando para números primos muito grandes. E sua única preocupação é evitar imprimir número primo intermediário pelo seu programa.

    Uma pequena mudança no seu programa fará o truque.

    Mantenha sua lógica da mesma forma e apenas retire a declaração de impressão fora do loop. Quebrar loop externo após n números primos.

     import java.util.Scanner; /** * Calculates the nth prime number * @author {Zyst} */ public class Prime { public static void main(String[] args) { Scanner input = new Scanner(System.in); int n, i = 2, x = 2; System.out.printf("This program calculates the nth Prime number\n"); System.out.printf("Please enter the nth prime number you want to find:"); n = input.nextInt(); for(i = 2, x = 2; n > 0; i++) { for(x = 2; x < i; x++) { if(i % x == 0) { break; } } if(x == i) { n--; } } System.out.printf("\n%d is prime", x); } } 

    Usando o Java 8 parallelStream seria mais rápido. Abaixo está o meu código para encontrar o número primo Nth

     public static Integer findNthPrimeNumber(Integer nthNumber) { List primeList = new ArrayList<>(); primeList.addAll(Arrays.asList(2, 3)); Integer initializer = 4; while (primeList.size() < nthNumber) { if (isPrime(initializer, primeList)) { primeList.add(initializer); } initializer++; } return primeList.get(primeList.size() - 1); } public static Boolean isPrime(Integer input, List primeList) { return !(primeList.parallelStream().anyMatch(i -> input % i == 0)); } @Test public void findNthPrimeTest() { Problem7 inputObj = new Problem7(); Integer methodOutput = inputObj.findNthPrimeNumber(100); Assert.assertEquals((Integer) 541, methodOutput); Assert.assertEquals((Integer) 104743, inputObj.findNthPrimeNumber(10001)); } 

    Embora muitas explicações corretas e detalhadas estejam disponíveis. mas aqui está minha implementação em C:

     #include #include main() { int pk,qd,am,no,c=0; printf("\n Enter the Number U want to Find"); scanf("%d",&no); for(pk=2;pk< =1000;pk++) { am=0; for(qd=2;qd<=pk/2;qd++) { if(pk%qd==0) { am=1; break; }} if(am==0) c++; if(c==no) { printf("%d",pk); break; }} getch(); return 0; }