Для заданного числа N я должен найти все простые числа, из которых он состоит

Question

Нужно предложение по алгоритму.

Для данного числа N мне нужно найти все простые числа, из которых оно состоит, например:

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

Если вы хотите помочь мне еще больше, вы можете написать алгоритм на с ++.

Спасибо.

Answer 1

Самый простой способ - пробное деление. В основном просто попробуйте разделить n на каждое простое число до sqrt (n). Для больших чисел это очень медленный алгоритм.

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

Для более сложных алгоритмов, попробуйте http://en.wikipedia.org/wiki/Integer_factorization