Calculadora de fatores primos

360 = 2^3 * 3^2 * 5; Omega(360) = 3 + 2 + 1 = 6; d(360) = (3+1) * (2+1) * (1+1) = 24

n

O número que está sendo decomposto — um inteiro de 1 a 1.000.000. A faixa é a que o módulo de teoria dos números usa em toda parte, então ela coincide exatamente com a da página de fatores e quem vai de uma para a outra encontra as mesmas bordas. Decimais são recusados em vez de arredondados, e 0 e negativos são recusados porque a fatoração em primos é uma afirmação sobre números inteiros positivos

p

Um fator primo — um primo que divide n exatamente. A página os encontra por divisão por tentativa em ordem crescente, então o menor primo é sempre retirado primeiro e a fatoração impressa sempre vai do menor primo ao maior. Para 360 os primos são 2, 3 e 5, e nenhum outro primo o divide

e

O expoente de um primo — quantas vezes ele aparece no produto. 360 é 2 × 2 × 2 × 3 × 3 × 5, então o 2 aparece três vezes e o 3 aparece duas. Um primo que aparece uma única vez é impresso sem expoente nenhum: o 5 de 360 é escrito como um 5 simples, e não como 5^1, que é a convenção usual e mantém as fatorações curtas legíveis

2^3 * 3^2 * 5

A fatoração de 360 como ela é impressa, e a entrada padrão. O acento circunflexo faz o papel do expoente e o asterisco o da multiplicação, então o conjunto todo sobrevive a ser copiado para um campo de texto simples ou para uma caixa de busca. Existe exatamente uma expressão assim para cada inteiro acima de 1, e é isso que a torna digna de ser impressa: 360 não pode ser escrito também como algum outro produto de primos

Omega(360) = 3 + 2 + 1 = 6

O número de fatores primos contando as repetições: três 2s, dois 3s e um 5 dão seis. É a contagem que surpreende, porque 360 parece ser construído de três primos, e não de seis. A receita é somar os expoentes, e não contar os primos distintos, e as duas respostas diferem sempre que algum expoente for maior que 1

d(360) = (3+1) * (2+1) * (1+1) = 24

O número de divisores positivos, obtido a partir dos mesmos expoentes somando um a cada um e multiplicando. A lista é 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180 e 360 — vinte e quatro deles. Esta é uma pergunta diferente da de cima: ela conta os números que dividem 360, e não os primos que o constroem

A fatoração é o que você quer quando a pergunta é sobre a estrutura multiplicativa de um número, e não sobre o tamanho dele. Simplificar uma fração ou uma raiz quadrada é o caso do dia a dia: a raiz quadrada de 72 se simplifica em 6√2 porque 72 = 2³ × 3², e o expoente de cada primo diz quanto dele pode sair de baixo do radical — é a mesma fatoração que a página de radicais lê. Achar um máximo divisor comum ou um mínimo múltiplo comum de dois números também é isto, feito uma vez por número: os primos comuns nos menores expoentes dão o primeiro, e todos os primos nos maiores expoentes dão o segundo. Perguntas de divisibilidade são respondidas do mesmo jeito, já que um número divide outro exatamente quando os primos e expoentes dele todos estão disponíveis no outro. Em teoria dos números a fatoração decide se um número é primo, quantos divisores ele tem, se é um quadrado perfeito (todo expoente par) e se é um cubo perfeito. Vale conhecer também os limites do método: a divisão por tentativa é rápida em um milhão e desesperadora em um número de cem algarismos, e essa distância entre o fácil e o difícil é exatamente aquilo sobre o que a criptografia de chave pública é construída. Quando a pergunta é quais números dividem o seu, e não quais primos o constroem, a página de fatores os lista; quando é se o número é primo, a página de números primos responde isso diretamente.

1. O caso padrão: 360

   1. 360 é par, então divide por 2: 360 / 2 = 180, depois 180 / 2 = 90, depois 90 / 2 = 45 — três vezes ao todo
   2. 45 não é par; o próximo primo é 3, e 45 / 3 = 15, depois 15 / 3 = 5 — duas vezes
   3. 5 é primo, então a fatoração é 2 × 2 × 2 × 3 × 3 × 5, escrita 2^3 * 3^2 * 5
   4. Conte os fatores primos com as repetições: 3 + 2 + 1 = 6
   5. Conte os divisores a partir dos expoentes: (3 + 1) × (2 + 1) × (1 + 1) = 4 × 3 × 2 = 24

   A entrada padrão, e a que mostra por que as duas contagens são impressas. Seis e vinte e quatro ficam um ao lado do outro, e quem espera que combinem vai achar que uma delas está quebrada. Não está: seis é de quantas peças primas o número é feito quando você mantém todas as repetições, e vinte e quatro é quantos números o dividem. A distância entre elas vem dos expoentes — cada repetição de um primo multiplica a contagem de divisores sem acrescentar quase nada à contagem de peças. Confira qualquer uma das duas à mão e a aritmética é curta; confira as duas e você vai lembrar qual é qual.

2. O caso pequeno que mostra a distância: 12

   1. 12 / 2 = 6, e 6 / 2 = 3, então o 2 aparece duas vezes
   2. 3 é primo, então a fatoração é 2^2 * 3
   3. Conte os fatores primos com as repetições: 2 + 1 = 3, que são 2, 2 e 3
   4. Liste os divisores: 1, 2, 3, 4, 6, 12 — seis deles
   5. Confira com a receita: (2 + 1) × (1 + 1) = 3 × 2 = 6, que bate com a lista

   O exemplo pequeno mais claro da confusão em torno da qual esta página foi construída, porque as duas contagens são pequenas o bastante para serem conferidas à mão em segundos. Doze é feito de três primos — 2, 2 e 3 — e seis números o dividem. Ler a saída como 3 divisores ou como 6 fatores primos soa plausível nas duas versões e está errado nas duas. A lista de divisores também mostra o emparelhamento que faz de seis uma contagem par: 1 com 12, 2 com 6, 3 com 4. Doze não é um quadrado perfeito, então nenhum divisor se emparelha consigo mesmo, e é por isso que a contagem é par.

3. O caso incômodo: 1

   1. 1 não é divisível por nenhum primo — dividir por 2, 3, 5 ou qualquer outro deixa uma fração
   2. Então não há fator primo nenhum, e a contagem deles é 0
   3. O único número positivo que divide 1 é o próprio 1, então a contagem de divisores é 1
   4. A fatoração é impressa como o algarismo 1, e não como um campo vazio

   O caso que precisa ser decidido, e não deduzido, e a decisão é imprimir 1. Deixar a fatoração em branco seria lido como uma falha de cálculo, que é a única coisa com que um painel de resultado nunca pode parecer. As duas contagens então caem honestamente: nenhum primo, e um divisor. O um não é primo nem composto — é o elemento neutro da multiplicação, o número que não muda nada quando você multiplica por ele — e a página não finge o contrário. Ele é aceito em vez de recusado porque a faixa de entrada começa em 1, e uma faixa que exclui o próprio valor inferior seria uma coisa mais estranha de se explicar.

A entrada precisa ser um número inteiro de 1 a 1.000.000. Zero é recusado: todo primo divide zero, então o produto teria de ser infinito. Números negativos são recusados por um motivo aparentado — os primos continuam dividindo, mas o sinal teria de ser carregado à parte e o enunciado de fatoração única é sobre números positivos. Decimais são recusados em vez de arredondados, já que arredondar responderia em silêncio a uma pergunta sobre outro número. O teto de um milhão vem do módulo de teoria dos números compartilhado e é uma questão de custo, não de correção: dividir por tentativa por todos os primos até a raiz quadrada é rápido em um milhão e desesperador em um número de vinte algarismos. Essa é uma fronteira genuína do método, e é a mesma fronteira que faz a criptografia de chave pública funcionar. A página informa a fatoração e duas contagens, e nada mais: não lista os divisores em si, não calcula um máximo divisor comum nem um mínimo múltiplo comum entre vários números, e não simplifica radicais nem frações. Um expoente igual a 1 nunca é impresso, então um primo que aparece uma única vez surge como um número solto, e o sinal de multiplicação é um asterisco do começo ao fim. Isso faz da fatoração um texto simples, com a grafia do sistema: um número que já é primo e tem quatro algarismos ou mais sai impresso sem separador de milhar — pedir 999983 devolve 999983, e não 999.983 —, ao passo que as duas contagens são números comuns e seguem a grafia do idioma. Na prática essas duas contagens nunca passam de 240, que é o maior número de divisores de qualquer inteiro abaixo de um milhão, então elas ficam sempre abaixo de mil e nunca chegam a exibir um separador. Por fim, a tabela de referência abaixo mostra quatro números fixos em vez de acompanhar a sua entrada.

Qual é a diferença entre as duas contagens desta página?

A primeira conta os fatores primos mantendo as repetições, a segunda conta os divisores. Para 12 as respostas são 3 e 6, e as duas estão certas. Doze é 2 × 2 × 3, então é feito de três peças primas; e 1, 2, 3, 4, 6 e 12 todos o dividem, então ele tem seis divisores. A confusão é natural porque os dois números ficam próximos em entradas pequenas. A receita da primeira é somar os expoentes; a receita da segunda é somar um a cada expoente e multiplicar. Essa multiplicação é a razão de a segunda contagem disparar muito mais rápido — cada repetição extra de um primo multiplica a contagem de divisores enquanto acrescenta apenas um à primeira.

Existe uma única fatoração em primos para um número?

Sim, e isso é um teorema, não uma convenção. Todo número inteiro acima de 1 pode ser escrito como produto de primos, e existe exatamente uma maneira de fazê-lo quando você ignora a ordem. Trezentos e sessenta é sempre 2³ × 3² × 5; ele não é também algum outro produto de primos. O resultado se chama teorema fundamental da aritmética, e sem ele imprimir uma fatoração seria uma curiosidade, e não uma resposta. É também por isso que a página pode imprimir o menor primo primeiro e ter certeza de que essa é a forma canônica — a ordem é escolhida pela legibilidade, e nada se perde ao fixá-la.

O que a página faz com o 1?

Imprime 1 como fatoração, com zero fatores primos e um divisor. O número 1 não é primo nem composto: ele não tem fatoração em primos no sentido usual, e é por isso que o teorema acima é enunciado para números acima de 1. Mas um painel de resultado vazio seria lido como falha de cálculo, então a página imprime o algarismo e informa as duas contagens honestamente. A contagem de divisores de 1 é mesmo 1, já que o único número positivo que divide 1 é o próprio 1, e a contagem de fatores primos é mesmo 0. O 1 é aceito em vez de recusado porque a faixa de entrada começa em 1, e recusar o próprio piso da sua faixa dá mais trabalho de explicar do que responder.

Por que a entrada para em um milhão?

Porque o método é a divisão por tentativa, e o custo dela cresce com a raiz quadrada do número. Achar os primos de um número perto de um milhão significa testar divisores até mil, o que é instantâneo. Achar os primos de um número de vinte algarismos significa testar até dez bilhões, o que não é. Essa distância não é um detalhe de implementação — é uma propriedade real do problema, e é a hipótese sobre a qual a criptografia de chave pública é construída, onde a dificuldade de fatorar números grandes é o que mantém uma mensagem privada. Dentro de um milhão toda resposta volta imediatamente, e o teto é declarado na entrada em vez de ficar escondido num tempo limite.

Quando eu ia querer uma fatoração em vez de uma lista de fatores?

Quando a pergunta é sobre estrutura, e não sobre quais números pertencem ao conjunto. Simplificar a raiz quadrada de 72 exige 72 = 2³ × 3², porque os expoentes dizem quanto de cada primo pode sair de baixo do radical, dando 6√2. Achar um máximo divisor comum entre dois números exige as duas fatorações, já que a resposta são os primos comuns nos menores expoentes. Verificar se um número é um quadrado perfeito é um olhar para os expoentes — todos pares significa sim. Listar divisores é outra pergunta, e dependendo do número a resposta pode ser bem mais longa: 720.720 tem 240 deles, o que é muito para imprimir e pouco para se olhar. A página de fatores deste site os lista quando é isso que você precisa.

Por que nenhum expoente é impresso quando um primo aparece uma vez?

Porque escrever 5^1 para um 5 solitário é ruído. Em matemática a convenção é imprimir o expoente apenas quando ele é maior que um, então 360 é 2^3 * 3^2 * 5 com o último termo sem expoente. Nada se perde ao deixá-lo de fora: a ausência de expoente significa que o expoente é um, sem ambiguidade, e uma fatoração feita só de primos solitários — que é o que um número livre de quadrados tem — se lê como um produto simples, sem acento circunflexo nenhum. A mesma convenção é a razão de 97, que é primo, ser impresso apenas como 97, e não como 97^1.

• Prime Factorization — writing a whole number as a product of primes, and the algorithms that find the primes — Wolfram MathWorld (United States)
• Fundamental Theorem of Arithmetic — the statement that every whole number above 1 has exactly one prime factorization, which is what makes printing it worth doing — Wolfram MathWorld (United States)
• Divisor Function — the count of positive divisors, the formula that builds it from the exponents, and how it behaves on powers of a single prime — Wolfram MathWorld (United States)