Árvore de Factorização Prima

A factorização prima decompõe um número inteiro nos números primos que, multiplicados, o produzem — a decomposição única que cada número composto tem, e apenas uma. Esta ferramenta pega em qualquer inteiro igual ou superior a 2 e factoriza-o de verdade, desenhando depois o resultado como a árvore de factores que se aprende na escola: comece com o número, separe o seu menor factor primo, e continue a dividir o que sobra até restarem apenas primos.

A regra de divisão é a divisão por tentativas pelo menor primo possível em cada passo: tente primeiro o 2, depois os ímpares 3, 5, 7, 9... até à raiz quadrada do valor actual. Para 360, isto desenrola-se como 360 = 2 × 180, depois 180 = 2 × 90, depois 90 = 2 × 45, depois 45 = 5 × 9, depois 9 = 3 × 3 — cinco divisões que terminam em seis folhas primas (2, 2, 2, 3, 3, 5). Contar essas folhas dá a forma compacta com expoentes mostrada sob o diagrama: 360 = 2³ × 3² × 5.

Tudo isto corre com aritmética exacta BigInt, por isso nunca há arredondamentos de vírgula flutuante pelo caminho. A divisão por tentativas até à raiz quadrada é rápida para números do dia-a-dia, mas torna-se mais lenta quanto maior for o menor factor primo do número, pelo que a ferramenta limita a entrada a 1.000.000.000.000 (10^12) e mostra uma mensagem honesta acima disso em vez de bloquear o separador — um browser não tem nada que ficar preso num semiprimo gigante só para provar um ponto.

Uma árvore de factores visual é a forma padrão como a factorização prima é ensinada na escola, e continua a ser útil muito para além da sala de aula: reduzir fracções, encontrar o máximo divisor comum ou o mínimo múltiplo comum comparando potências de primos, simplificar raízes quadradas e verificar rapidamente se um número é primo — tudo se resume à mesma decomposição. Tudo corre localmente no seu browser — sem registo, sem comunicação com o servidor.