Calculadora de números primos

n é primo <=> d(n) = 2; previousPrime(97) = 97; nextPrime(97) = 97; nextPrime(1.000.000) = 1.000.003

n

O número inteiro que está sendo testado — de 2 a 1.000.000. O limite inferior é deliberado, e não herdado: o primo anterior de 1 não existe, então uma página que aceitasse 1 teria uma linha que ela não conseguiria preencher com honestidade. Se 1 é primo é uma questão de definição e é respondida nas perguntas abaixo, não pela calculadora

d(n)

O número de divisores positivos, que é a primeira linha do resultado e a única evidência em que o veredito se apoia. d(n) = 2 significa que exatamente dois números o dividem, que é a definição de primo. A contagem vem da rotina compartilhada de teoria dos números, então é o mesmo valor que a página de fatores e a página de fatoração em primos informam para a mesma entrada

d(n) = 2

O teste em si, enunciado como uma equação. É uma equivalência, e não uma aproximação: um número é primo se e somente se tem exatamente dois divisores. Para 97 os divisores são 1 e 97, então a contagem é 2 e o selo lê primo. Para 100 eles são 1, 2, 4, 5, 10, 20, 25, 50 e 100, então a contagem é 9 e o selo lê composto

previousPrime(n)

O maior primo que é menor ou igual a n. Ele é inclusivo no topo, então quando n é primo a resposta é o próprio n. Para 100 a resposta é 97; para 25 é 23; para 97 é 97. O intervalo é fechado porque a alternativa exigiria uma regra para o que imprimir quando n já é primo, e uma linha em branco num painel de resultado é lida como uma falha, e não como um fato

nextPrime(n)

O menor primo que é maior ou igual a n, com a mesma regra inclusiva na base. Para 25 é 29, para 100 é 101, e para 97 é 97. Este pode sair da faixa da entrada: nextPrime(1.000.000) é 1.000.003, um primo maior que qualquer número que a página aceita, e ele é informado como resposta em vez de tratado como fora dos limites

1e6 to 1e6 + 100

A vizinhança do teto da entrada, e por que é preciso um teste separado lá em cima. Os primos perto de um milhão são 999.983 e 1.000.003, então a busca a partir de 1.000.000 precisa olhar para além de um milhão em uma das direções. A rotina que conta divisores recusa argumentos acima de um milhão e lançaria um erro, então a busca de vizinhos usa um teste próprio, sem esse limite — e os dois precisam concordar onde quer que se sobreponham, que é o que as linhas de primo nos exemplos verificam

Escolher um módulo é a razão mais prática de querer um primo perto de um número que você já escolheu. O número de posições de uma tabela hash costuma ser primo, porque um módulo primo espalha chaves que compartilham um fator comum em vez de deixá-las colidir; uma tabela com 1.000 posições manda todos os múltiplos de 25 para as mesmas poucas posições, enquanto uma com 997 não faz isso. O mesmo instinto vale em criptografia, onde as chaves são construídas a partir de primos grandes e distantes entre si. Verificar se um número é primo também resolve perguntas de divisibilidade rapidamente: se um número não tem nenhum divisor primo até a sua raiz quadrada, ele não tem nenhum, e o selo responde isso em um passo em vez de por tentativa. Alguns quebra-cabeças são simplesmente sobre primalidade — primos gêmeos, as distâncias entre primos consecutivos e se um número dado é o produto de dois primos. Quando a pergunta acaba sendo sobre os fatores em si, a página de fatoração quebra o número em primos e é a parada natural seguinte; quando é sobre quais números dividem o seu, a página de fatores os lista todos; e quando o número testado não é primo e você quer saber de que ele é feito, a contagem de divisores desta página é a primeira pista, e não a resposta completa.

1. Um primo: 97

   1. Teste os divisores de 97: 2 não o divide, e 3, 5 e 7 também não
   2. Pare na raiz quadrada: 10 × 10 = 100 já passou de 97, então não sobrou nada para testar — o próximo primo, 11, está além desse corte
   3. Os únicos divisores são 1 e 97, então a contagem é 2 e o número é primo
   4. O primo anterior é o próprio 97, porque 97 já é primo e a busca é inclusiva
   5. O próximo primo também é 97, pelo mesmo motivo

   A entrada padrão, e a ilustração mais limpa da regra inclusiva. Os dois vizinhos voltam como o próprio número, o que à primeira vista parece que as linhas não fizeram nada. Fizeram: o maior primo que não passa de 97 é 97, e o menor primo que não fica abaixo de 97 também é 97. A alternativa — uma desigualdade estrita — deixaria essas duas linhas sem nada para imprimir exatamente nas entradas em que a página está mais segura, e uma linha em branco num painel de resultado é lida como erro. Este caso é também onde os dois testes independentes da página se encontram: a contagem de divisores diz 2, e a busca de vizinhos concorda que 97 é primo, e os dois chegam lá por código diferente.

2. Um número composto: 100

   1. 100 é par, então 2 o divide; ele termina em 00, então 4, 5, 10, 20, 25 e 50 também o dividem
   2. Os divisores são 1, 2, 4, 5, 10, 20, 25, 50 e 100 — nove deles
   3. Nove é mais que dois, então o selo lê composto, e não primo
   4. O maior primo menor ou igual a 100 é 97; o menor maior ou igual a ele é 101
   5. Os dois vizinhos ficam a um passo do número, que é a cara de um número composto no meio de um intervalo

   O caso que mostra os vizinhos fazendo trabalho de verdade. Quando um número é composto, as duas linhas são a saída útil, porque respondem à pergunta que o leitor tem em seguida: se não é este número, qual é? Noventa e sete e cento e um são os primos mais próximos, e o 100 fica entre eles. A contagem de divisores igual a nove também merece um olhar — ela é ímpar, o que acontece exatamente quando o número é um quadrado perfeito, e 100 é 10 ao quadrado. Então um único olhar para a contagem já diz algo sobre a forma do número, antes de qualquer fatoração.

3. Um número logo depois de um primo: 25

   1. Os divisores de 25 são 1, 5 e 25 — três deles, porque o 5 se emparelha consigo mesmo
   2. Três é mais que dois, então 25 é composto
   3. Desça a partir de 25: 24, 23 — 23 é primo, então é o primo anterior
   4. Suba a partir de 25: 26, 27, 28, 29 — 29 é primo, então é o próximo primo
   5. A distância aqui é de seis no total: 23 e 29 ladeiam o 25

   Um quadrado perfeito, que é a razão de a contagem de divisores ser ímpar, e um caso em que os dois vizinhos estão a distâncias visivelmente diferentes — dois abaixo e quatro acima. A contagem igual a três mostra também por que dois é o limiar certo, e não uma contagem de fatores primos: 25 tem um único fator primo, o 5, mas não é primo, e a contagem de divisores capta isso sem precisar olhar para a fatoração.

A entrada precisa ser um número inteiro de 2 a 1.000.000. Zero e um são recusados, e o um é recusado por um motivo diferente do zero: ele é uma questão de definição, e não um número fora da faixa, e o primo anterior de 1 não existe. Números negativos são recusados — a primalidade é uma propriedade dos inteiros acima de 1, e embora exista uma convenção para primos negativos em alguns ramos da matemática, esta página não adota nenhuma. Decimais são recusados em vez de arredondados. O teto de um milhão vale apenas para a entrada; as duas linhas de vizinhos podem legitimamente informar um primo fora dele, e o próximo primo depois de um milhão é 1.000.003, que é informado em vez de recusado. O teste por trás do veredito é a divisão por tentativa até a raiz quadrada, que é instantânea neste tamanho e desesperadora num número de vinte algarismos, e essa fronteira é uma propriedade do problema, não desta implementação. A página informa três números e um selo: não lista os divisores em si, não fatora um número composto, e testa um número por vez em vez de um intervalo. A tabela de referência abaixo tem linhas fixas em vez de responder à sua entrada. Por fim, um primo é informado como o próprio primo anterior e o próprio próximo primo, o que é uma escolha deliberada de intervalo inclusivo, e não duas linhas que não acharam nada.

O 1 é um número primo?

Não, e também não é um número composto. Um primo é definido como um número inteiro maior que 1 com exatamente dois divisores positivos, e o 1 tem apenas um divisor, então ele falha na definição nos dois sentidos. Isso é uma escolha deliberada, e não um descuido: se o 1 fosse contado como primo, a afirmação de que todo número tem exatamente uma fatoração em primos deixaria de ser verdadeira, porque você poderia multiplicar uma fatoração por 1 quantas vezes quisesse. Excluir o 1 é o que mantém esse teorema limpo. Como é uma questão de definição e não de aritmética, a página não aceita 1 como entrada — a resposta mora aqui.

Por que o primo anterior e o próximo primo voltam como o próprio número?

Porque as duas buscas são inclusivas. O primo anterior é o maior primo que não é maior que o seu número, e o próximo primo é o menor primo que não é menor que ele. Quando o número já é primo, ele satisfaz as duas descrições, então as duas linhas o informam. A alternativa seria uma desigualdade estrita, e aí uma entrada prima deixaria duas linhas sem nada para imprimir. Uma linha em branco num painel de resultado é lida como algo dando errado, e a página ficaria sem resposta justamente no caso em que tem mais certeza de si. A mesma convenção aparece no arredondamento, onde um número que já está na precisão pedida volta sem mudança.

Por que o próximo primo pode ser maior que um milhão se a entrada não pode?

Porque o teto é um limite sobre o que você pode perguntar, e não sobre o que a resposta pode ser. O próximo primo depois de 1.000.000 é 1.000.003, e recusar imprimi-lo significaria recusar responder a uma pergunta perfeitamente bem formulada sobre uma entrada que a página aceitou. Então a busca de vizinhos roda com um teste próprio, sem limite superior, enquanto a contagem de divisores continua usando a rotina compartilhada, que só cobre a faixa. Isso significa que duas partes da lógica decidem se um número é primo — uma limitada, outra não — e elas precisam concordar onde quer que se sobreponham, que é o que o exemplo do 97 verifica: a contagem diz 2, e a busca de vizinhos diz que 97 é primo.

Para que serve um número primo, na prática?

Para dimensionar coisas, principalmente. Tabelas hash costumam receber um número primo de posições, porque um módulo primo espalha chaves que compartilham um fator comum — uma tabela com 1.000 posições manda todos os múltiplos de 25 para as mesmas poucas posições, enquanto uma com 997 não faz isso. O mesmo raciocínio vale para qualquer contador que dá a volta: um comprimento de ciclo primo evita ressonância com padrões regulares dos dados. A criptografia é o outro grande uso, onde as chaves são construídas a partir de primos muito grandes e distantes entre si, e a segurança se apoia em quão difícil é fatorar o produto deles de volta nos dois primos de origem. Os usos menores estão por toda parte: conferir uma afirmação de divisibilidade, testar se um número é o produto de dois primos, e os quebra-cabeças clássicos sobre primos gêmeos e as distâncias entre primos consecutivos.

Como a página decide, e quão segura ela é?

Contando divisores, o que é exato e não probabilístico. Um número é primo se e somente se tem exatamente dois divisores positivos, então a contagem resolve a questão sem possibilidade de resposta errada e sem precisar confiar num teste que possa ser enganado. A contagem é feita por divisão por tentativa até a raiz quadrada, e é por isso que um milhão é o teto: passando disso o método fica lento, e não duvidoso. Para números muito maiores os métodos exatos são genuinamente inviáveis e usam-se testes probabilísticos, mas neste tamanho não há razão para aceitar nada menos que certeza, e a página não aceita.

Por que a contagem de divisores aparece, e não só o veredito?

Porque a contagem é a razão do veredito, e mostrá-la faz com que os dois nunca possam discordar — o selo não é um segundo cálculo, mas uma leitura do número impresso ao lado dele. Ela também é útil por si só. Uma contagem ímpar significa que o número é um quadrado perfeito, já que a raiz quadrada se emparelha consigo mesma em vez de com um divisor diferente. Uma contagem igual a 2 é a definição de primo. Uma contagem grande em relação ao tamanho do número diz que ele tem muitos fatores pequenos, que é o tipo de número que junta divisores depressa. E ela liga esta página às outras: a página de fatoração em primos informa a mesma contagem de divisores para a mesma entrada, calculando-a a partir dos expoentes, então as duas páginas se conferem.

• Prime Number — the definition, the divisor-count test, and why 1 is excluded by it — Wolfram MathWorld (United States)
• Prime Gaps — the distances between consecutive primes, and what the neighbourhood of a million looks like — Wolfram MathWorld (United States)
• Composite Number — the complement of the primes, and why 1 belongs to neither group — Wolfram MathWorld (United States)