[avisitor]

Does anyone happen to know of an algorithm for calculating the prime factors of a 32bit integer. I tried Googling, but I didn't really come up with anything. I see there's an FFT algorithm for this, but is that just for matrices? I know I can just repeatedly divide in, but that's terribly slow and inefficient when you've got tens of thousands of integers you want to calculate the factors of.

Despite how this sounds, it's not a homework problem, rather, it's just a project I'm working on. Thanks in advance.

[etaf]

have a read here - how to set up excel
http://people.revoledu.com/kardi/tut...rimeFactor.htm

[avisitor]

Right, that's the divide method. Is there any other way besides that?

[IMM]

You could look at this http://en.wikipedia.org/wiki/Lenstra..._factorization and the external link at the bottom hxxp://alpertron.com.ar/ECM.htm which offers java source -- but with your max of about 2^31, then the prime factors are less than square root of 2^31 (about 2^16) and you may just want to use a table of primes method?

[avisitor]

Yeah, the table of primes is how I ended up implementing it. Thanks for the suggestions.

[lotuseclat79]

Take a look at Sieve of Eratosthenes.

-- Tom

[BobFoster]

My understanding of this problem in general is that it is a "hard" problem to solve - i.e. there's no short cut method, at least not one that shaves much off the simple brute-force methods you've investigated.

The difficulty in solving this problem (for very large numbers, bigger than 32 bit ints) is relied upon in cryptography algorithms such as RSA. If you could find the prime factors of the large numbers used (say 512 bits), you could break RSA. RSA is used on the basis that it would be infeasible to find the factors even with years of computer time.

If you've Googled around the problem (or perhaps anyway), you probably know this, but I thought I'd throw in my two penneth.

My quick Google came up with a recommendation for the Pollard-Strassen method, which (according to Mathworld) is the most efficient algorithm known. I haven't investigated how easy it would be to implement.

Regards,
Bob