Este script calcula a decomposição de um número natural n em seus fatores primos. Ele retorna uma lista contendo dois elementos: um vetor com os números primos que dividem n, ordenados de modo crescente, e um vetor com os expoentes correspondentes aos fatores primos. Se n for primo, obviamente n será o único fator, com expoente igual a 1.
Dado n, no máximo um divisor (e com expoente igual a 1) será maior que a raíz quadrada de n. Isso segue do Teorema Fundamental da Aritmética. Deste modo, meu método consiste em utilizar o Crivo de Eratóstenes para gerar os números primos até raíz(n). Opcionalmente, posso passar ao script um crivo já calculado, desde que, é claro, o maior primo constante nesta lista seja maior ou igual a raíz(n). Isso torna o script bem mais rápido.
Nenhum comentário:
Postar um comentário