Menor fator primo

O menor fator primo de um inteiro é o menor primo que o divide exatamente. Se o número é primo, esse fator é o próprio número; se é composto, é o primeiro primo da fatoração e o certificado mais barato de que o valor não é primo.

O que é o menor fator primo e o que esta ferramenta devolve

Todo inteiro n maior que um tem um multiconjunto único de fatores primos pelo teorema fundamental da aritmética, e entre esses primos sempre existe um mínimo. Esse valor chama-se menor fator primo, muitas vezes abreviado SPF em tabelas de teoria dos números e em problemas de programação competitiva. Quando n é primo, o SPF é n; quando n é par, o SPF é sempre dois; quando n é produto de primos maiores, o SPF é o primeiro primo que divide n na tentativa ordenada.

Esta capacidade responde apenas a essa pergunta: não lista cada potência prima, não calcula a função totiente de Euler e não emite certificados de primalidade para inteiros de milhares de bits.

Como funciona o algoritmo de tentativa determinística

O motor verifica primeiro a divisibilidade por dois e por três, porque múltiplos pares e de três dominam as entradas do dia a dia e resolvem-se em tempo constante. Os candidatos restantes percorrem uma roda de seis passos da forma 6k±1 a partir de cinco, que salta todo inteiro divisível por dois ou três e ainda assim atinge todo primo. Assim que um candidato divide n, esse candidato é devolvido como menor fator primo — não é preciso continuar a busca porque os candidatos são testados em ordem crescente.

Se o laço chega à raiz quadrada inteira de n sem achar divisor, n deve ser primo e é devolvido como seu próprio menor fator primo. Toda a aritmética usa BigInt internamente dentro do intervalo de inteiro seguro publicado para que produtos intermediários fiquem exatos; em seguida os resultados são serializados como números JavaScript ordinários na resposta.

Onde um calculador do menor fator primo se encaixa em fluxos reais

Estudantes e professores usam uma calculadora do menor fator primo para verificar tarefas, mostrar por que um número falha numa afirmação de primalidade ao nomear o primeiro primo obstrutivo e construir intuição antes da fatoração completa. Desenvolvedores de aplicações chamam-na quando um pipeline só precisa do menor fator — por exemplo para remover a paridade, para uma tentativa ao estilo Pollard antes de métodos mais pesados, ou para rejeitar valores de configuração obviamente compostos com um primo concreto em vez de um simples false.

Engenheiros de dados filtram colunas numéricas que deveriam ter forma de primo: qualquer valor cujo SPF seja menor que o próprio valor é composto, e o fator entra no registo de auditoria sem expandir a lista completa de fatores. Solucionadores de contests e APIs educativas expõem o SPF como primeiro bloco rumo a contagens omega, radicais e tabelas de crivo.

Prefira esta ferramenta quando a intenção de busca for estritamente «qual é o menor fator primo de n?», não quando precisar de cada potência prima, certificados de primalidade para inteiros multiprecisão enormes ou testes probabilísticos com listas de testemunhas personalizadas.