最大公約数・最小公倍数・素因数分解

最大公約数

ユークリッドの互除法を用いて求めます。

※C++17以降はstd::gcdを用いることができます。C++14でも、GCCを使用している場合は__gcdを使用することができます。

最小公倍数

ab = gcd(a,b) * lcm(a,b)
⇔ lcm(a,b) = ab / gcd(a,b)

割り算を先に行ったほうが安全です。(オーバーフロー対策)

素因数分解

素因数である可能性のある数をforで回してひたすら求めます。
ここでは簡単のためにやりませんが、 2, 3, 5, 7, …と2以外は奇数を数えたほうが少し高速化されます。

エラトステネスの篩を使用すれば候補を絞る事ができますが、n > 10^8くらいにならないと効果が得られない模様。
競技プログラミング界隈では、かえって実行速度は落ちると思います。

使い方

std::mapはstd::pair<const key, value>のコンテナで実装されています。

約数の個数

関連問題

約数の列挙

素因数分解してbit全探索〜なんて考えないほうがいい。いやまじで。

コードは下記ページを参考に作成しました。

関連問題