数学豆知識まとめ
せっかくAOJなどで学んだ数学の豆知識をまとめておこうとおもう。
人は忘れる生き物だから。
ここにどんどん追記していきたい。
素数判定
「合成数 は を満たす素因子 をもつ」
合成数xが素数かどうかはルートxまでの値で割れるかどうか見ればいいということ。
xの値まで調べるとするとO(x)となる。
でもxの半分まで調べればいいんじゃない?と気がつくと。O(x/2)
ルートのことに気がつくとO( )という風に処理が速くなるぞ。
普段、素数判定なんて、もちろんしないが、処理速度の意識はしたい。
5は素数かどうか。
mod(4^5,5) = 1024/5 の余りは4
というようにべき乗の元の数?と余りが一致する。
nは素数か?
a < nの範囲で調べる
a^n%n = a になる場あり、素数の確率が高い。
という判定法でした。
最大公約数判定 ユークリッドの互除法
「整数 x, y について、x ≥ y ならば x と y の最大公約数は y と x % y の最大公約数に等しい。」
n進数の各桁を足して、割り切れる数字
「n進数はn-1で割れる場合とそのn-1の約数が対象の数字となる。」
10進数の場合、例えば666、各桁を足して、9で割れる場合、それは9の倍数。
3で割れる場合、それは3の倍数。113は各桁を足すと5、でも5の倍数ではない。
10進数における3と5の差は?
さて、それがn進数の場合は?
9進数で44 = 4*9 + 4 = 40(10進数) 各桁を足すと4+4=8、40も8も8(n-1)で割ることができる。その約数である、2でも4でも割れる。
n-1とその約数が答えなのだ。