[RESOLVED] Prime Factors

[BlindSniper]

Hi all,
Today I started to implement methods to calculate the divisors of a number efficiently, and the only working algorithm I could implement was trial Division(after I red pseudo code that basically was vb). It worked fine, but now I'm trying to find the divisors of a big number and seeing how BigInteger doesn't have a Sqrt function, my little trial division function was left out in the dark.

I did a bit of Research and found Msieve and It works pretty well, but it give's the output in Prime Factors, and I really only need Divisors, is there some way to derive the divisors from prime factors ?

[jemidiah]

If a number n has prime factorization
n = p1^a1 * p2^a2 * ... * pk^ak

where the numbers p1, ..., pk are distinct primes and the exponents a1, ..., ak are positive integers, any factor f of n is of the form

f = p1^b1 * p2^b2 * ... * pk^bk

where each exponent bi is between 0 and ai. As an example, the number 12 is 2^2 * 3^1. Its factors are
2^2 * 3^1 = 12
2^1 * 3^1 = 6
2^0 * 3^1 = 3
2^2 * 3^0 = 4
2^1 * 3^0 = 2
2^0 * 3^0 = 1

To compute every factor from the prime factorization requires you to loop over all choices of bi, which results in k nested loops. It's easy to see from the rule of product that there are precisely (a1 + 1)*(a2 + 1)*...*(ak + 1) different factors, where the ai are as above.

[BlindSniper]

Thank you, I Need to rep you twice now, but can't yet.