Fatorar Número em Primos

Fatorar um número em primos é escrevê-lo como uma multiplicação de números primos, aqueles divisíveis apenas por 1 e por si mesmos. Por exemplo, 360 fatorado fica 2^3 x 3^2 x 5, ou seja 2 x 2 x 2 x 3 x 3 x 5. Os primos funcionam como as peças básicas dos números inteiros, já que qualquer número maior que 1 pode ser construído multiplicando primos. A forma compacta usa expoentes para agrupar fatores repetidos, e a forma expandida mostra o produto inteiro, deixando visível cada primo que entra na composição.

A fatoração usa divisões sucessivas pelos menores primos possíveis até sobrar 1. Começa-se testando o 2: enquanto o número for par, divide-se por 2 e anota-se o fator; depois passa-se para 3, 5, 7 e assim por diante, sempre pelo próximo primo que divide o valor. Para 84: dividindo por 2 dá 42, por 2 de novo dá 21, por 3 dá 7, e 7 é primo, encerrando em 2^2 x 3 x 7. Basta testar primos até a raiz quadrada do número; se sobrar algo maior que 1, ele próprio é primo.

Todo número inteiro maior que 1 tem uma única fatoração em primos, resultado conhecido como Teorema Fundamental da Aritmética. Não importa a ordem em que você faça as divisões, o conjunto de fatores primos e seus expoentes sempre será o mesmo. Essa unicidade é o que torna a fatoração tão útil: é a base para calcular MMC e MDC, simplificar frações e entender divisibilidade. Também é o motivo de os primos serem centrais na criptografia, já que fatorar números muito grandes é uma tarefa lenta mesmo para computadores.