Verificador de superprimo

Um superprimo, também chamado superprimo ou primo de índice primo, é um número primo cuja posição na sequência de todos os primos é, ela própria, um primo. Os primos ordenados começam em dois, três, cinco, sete, onze, treze e dezessete; seus índices (a partir de um) vão de um a sete. Os índices dois, três, cinco e sete são primos, portanto três, cinco, onze e dezessete são superprimos, enquanto dois (índice um) e sete (índice quatro) são apenas primos comuns. Este verificador aceita um único inteiro n. Quando n é primo a resposta devolve o índice de n e se esse índice é primo. O algoritmo é um crivo determinístico, sem rede, aleatoriedade ou relógio.

O que é um superprimo e como o veredito é formulado

Um superprimo se define por duas condições de primalidade aninhadas. Primeiro, n precisa ser primo: não tem divisor positivo além de um e de si mesmo. Segundo, se n é o k-ésimo primo na sequência crescente usual —p um vale dois, p dois vale três, p três vale cinco, p quatro vale sete, p cinco vale onze, e assim por diante—, então k também precisa ser primo.

O índice k é exatamente o valor da função de contagem de primos π(n) sempre que n é primo, porque π(n) conta quantos primos são menores ou iguais a n, e n ocupa essa última vaga. A sequência de superprimos começa portanto em três, cinco, onze, dezessete, trinta e um, quarenta e um, cinquenta e nove, sessenta e sete, oitenta e três, cento e nove: são os primos nos índices primos dois, três, cinco, sete, onze, treze, dezessete, dezenove, vinte e três e vinte e nove.

Observe que dois, igual a p um, fica de fora porque um não é um índice primo, e que sete, igual a p quatro, fica de fora porque quatro é composto.

Contrato de entrada, limites e como o índice é calculado

Depois de aceitar o inteiro, o motor primeiro testa se n é primo por divisão por tentativa em uma roda de seis passos. Se esse teste falhar, a solicitação é rejeitada com uma mensagem de que n não é primo; essas falhas não são cobradas. Se n é primo, o motor executa o crivo de Eratóstenes no intervalo de zero até n, conta quantos inteiros sem marca ficam em ou abaixo de n e trata essa contagem como o índice k a partir de um.

Um segundo teste por tentativa decide então se k é primo. Prefira um verificador de primo dedicado quando só precisar de um sim ou não sobre n, e uma calculadora do n-ésimo primo quando já souber o índice e quiser o primo em si. Esta página responde à pergunta combinada: dado um primo, o índice dele também é primo?

Onde um verificador de superprimo agrega valor

Salas de aula e treinadores de olimpíadas usam um verificador de superprimo para que aprendizes classifiquem primos de índice primo sem montar um crivo à mão nem confiar em uma lista opaca na internet. Geradores de prova precisam de um oráculo determinístico que marque compostos como entrada inválida em vez de devolver false em silêncio, porque um corretor defeituoso poderia tratar essa bandeira como classificação bem-sucedida de um não primo.

Cadernos que filtram uma coluna de primos candidatos até restarem superprimos podem chamar o contrato uma vez por célula e guardar o índice devolvido para uma coluna de auditoria. Combine esta ferramenta com um verificador de primo quando quiser classificar compostos em vez de rejeitá-los, e com uma calculadora do n-ésimo primo quando quiser percorrer a sequência por índice em vez de testar um candidato que você já tem em mãos.