数論の基礎と応用
因数に関する考察
1からnまでのすべての数の因数の総数はO(n log n)である。
1からnまでの素数の個数はO(n / log n)である。
伯トラン・チェビシェフの定理：n ≥ 1のとき、nと2nの間に少なくとも1つの素数がある。
直角三角形の辺の長さの一般式：a = w * 2uv, b = w * (u^2 - v^2), c = w * (u^2 + v^2)、ここでu, v, wは正の整数。
問題
Common Divisors: a_1, a_2, ...
6月22日 20:48 投稿
最大公約数と最小公倍数のアルゴリズム
最大公約数 (GCD)
2つの整数 a と b の最大公約数（GCD）とは、両方を割り切ることができる最大の整数を指します。記号では gcd(a, b) と表されます。
例えば、gcd(15, 18) と gcd(-15, -18) はどちらも 3 になります。
ユークリッドの互除法
最大公約数を求める代表的な方法として、ユークリッドの互除法が知られています。
このアルゴリズムの仕組み：
大きい数を小 ...
5月17日 14:51 投稿