Achar Divisores de um Número em C++

[Ítalo Spedini 0]

Olá a todos, queria saber como faço para achar o número de divisores de um número, sem ter que usar força bruta indo de 1 até o número a ser pesquisado e testando se deixa resto zero. Vi em um tópico o algoritmo que uma moderadora postou, mas está em Python, daí não entendi.

 

Obrigado.

[Felipe_Volpatto 1]

Bom dia,

 

Bá cara, eu desconheço essa outra técnica.

O que você pode fazer é, realmente, o que você citou.

Um loop do 1 até a metade do número desejado e uma var contadora embaixo para contar quantos divisores há.

 

Abraço.

[Motta 645]

Até onde saiba é um NP.

 

Só na força bruta.

 

Se existir um algoritmo mais rápido os métodos de criptografia baseados em números primos estão lascados.

[_Isis_ 202]

Se for o tópico do AKS, aquilo não serve porque é um teste de primalidade, e não um algoritmo de fatoração.

Existe um método de formas quadráticas que não deve ser muito difícil de implementar (ao contrário de alguns algoritmos que dependem de escolhas aleatórias de polinômios enormes)

 

http://cadigweb.ew.usna.edu/~wdj/mcmath/TridentFinal.pdf

http://www.usna.edu/Users/math/wdj/mcmath/shanks_analysis.pdf

http://www.usna.edu/Users/math/wdj/mcmath/shanks_squfof.pdf

http://homes.cerias.purdue.edu/~ssw/squfof.pdf

http://programmingpraxis.com/2010/08/24/daniel-shanks-square-form-factorization-algorithm/

[Ítalo Spedini 0]

Se for o tópico do AKS, aquilo não serve porque é um teste de primalidade, e não um algoritmo de fatoração.

Existe um método de formas quadráticas que não deve ser muito difícil de implementar (ao contrário de alguns algoritmos que dependem de escolhas aleatórias de polinômios enormes)

 

http://cadigweb.ew.usna.edu/~wdj/mcmath/TridentFinal.pdf

http://www.usna.edu/Users/math/wdj/mcmath/shanks_analysis.pdf

http://www.usna.edu/Users/math/wdj/mcmath/shanks_squfof.pdf

http://homes.cerias.purdue.edu/~ssw/squfof.pdf

http://programmingpraxis.com/2010/08/24/daniel-shanks-square-form-factorization-algorithm/

 

O tópico que vi foi você mesmo que tinha postado :D . Vou dar uma olhada nos links que você passou, e vi um método também de fatorar e depois multiplicar os expoentes dos numeros primos + 1. Ex: 60 = 2^2 + 3^1 + 5^1 , o número de divisores será (2+1)*(1+1)*(1+1) = 12, já contando o 1 e o 60. Vou tentar implementar desta forma.

 

Obrigado a todos.

[guidjos 65]

Se o método citado for o de testar todos os restos de divisão de n (entrada) por x, sendo x = {2, ..., n^(1/2)}, x inteiro (obviamente), testa-se a primalidade em O(n). Deve haver um meio de estender o algoritmo para divisores em geral.

[quitZAUMMM 18]

Talvez ajude: http://pt.wikipedia.org/wiki/Crivo_de_Erat%C3%B3stenes

 

[]s