Como encontrar todos os fatores principais em um número inteiro longo não assinado?

Question

Eu tenho uma tarefa para encontrar todos os principais fatores de um número ...

Preciso escrever uma função que leva um número e me diga todos os principais fatores do número. Por exemplo:

• n = 350 fatores primos: 2 5 5 7

(Passo para a função um número no intervalo de 0 a 18446744073709551615 - o número máximo é o maior número que se encaixa em um número inteiro comprido de comprimento de 64 bits não assinado.)

Answer 1

Esse é um problema difícil e uma das principais razões para todas as pesquisas sobre computadores quânticos. Dar uma olhada em Algoritmo de Shor. A força bruta simples sem otimizações levaria algo como 1000 anos, embora neste caso específico (números inteiros de 64 bits), você deva reduzir o tempo de execução para apenas alguns minutos.

Supondo que você tenha um caso trivial de (no máximo) um grande fator principal, você pode acelerar significativamente fazendo algo como contar com 2 e tentar cada número (várias vezes se funcionar; 12 seria 2, 2 e 3 para exemplo). Depois de encontrar um fator, reduza seu número de destino por esse fator e teste se o novo alvo é o Prime.

Para acelerar ainda mais, você pode fazer processamento em vários threads, com cada um responsável por uma variedade de divisores. Você pode executar testadores de primalidade em um ou mais threads, fornecendo primos ao thread de teste para que você esteja apenas tentando se dividir por números primos.

Você pode até procurar a partir do topo da faixa, se você acha que a pessoa que fornece o valor está tentando ser complicada, embora com a densidade de números primos seja muito maior na extremidade baixa, isso provavelmente não ajudará.

A principal coisa a lembrar, porém, que o maior fator possível de X, além de X em si, é a raiz quadrada de X. Cada vez que você encontrar um fator, o maior fator restante possível diminui significativamente.