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

最大公約数

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

※C++17以降はstd::gcdを用いることができます。C++14でも、GCCを使用している場合は__gcdを使用することができます。
AtCoderのC++はC++17になり、std::gcdが使えるようになりました。

最小公倍数

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

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

※C++17以降はstd::lcmを用いることができます。

素数判定

2, 3以降の素数は6で割ったときの余りが1または5、という特性を活かすと少しだけ高速化できます。
定数倍でしか早くならないですが…

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

素因数分解

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

使い方

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

約数の個数

関連問題

約数の列挙

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

関連問題