c++ - 与えられた数 N に対して、それが構成するすべての素数を見つけなければなりません

Question

アルゴリズムの提案が必要です。

与えられた数 N に対して、次のように、それを構成するすべての素数を見つける必要があります。

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

さらに私を助けたい場合は、C++ でアルゴを書くことができます。

ありがとう。

Answer 1

最も簡単な方法は試行割り算です。基本的には、nをsqrt（n）までの各素数で割ってみてください。多数の場合、これは非常に遅いアルゴリズムです。

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

より洗練されたアルゴリズムについては、http：//en.wikipedia.org/wiki/Integer_factorizationを試してください