1

Need a suggestion for an algorithm.

For a given number N i have to find all the prime numbers it's consisting of, like this:

N = 49
49 = 7 ^ 2
N = 168
168 = (2 ^ 3) * (3 ^ 1) * (7 ^ 1)

If you want to help me even more you can write the algo in c++.

Thanks.

4

1 回答 1

3

The most straightforward way is trial division. Basically just try dividing n by each prime number up to sqrt(n). For large numbers, this is a very slow algorithm.

http://en.wikipedia.org/wiki/Trial_division

For more sophisticated algorithms, try http://en.wikipedia.org/wiki/Integer_factorization

于 2010-02-19T21:03:00.480 回答