CODEWITHSUNDEEP
c++algorithmprimes
ggg
ggg

Reputation: 965

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

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.

Upvotes: 1

Views: 844

Answers (1)

Joel
Joel

Reputation: 5674

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

Upvotes: 3

Related Questions