数学豆知識その1 - てぃぐれのプログラマwiki

数学豆知識まとめ

せっかくAOJなどで学んだ数学の豆知識をまとめておこうとおもう。

人は忘れる生き物だから。

ここにどんどん追記していきたい。

素数判定

「合成数 $x$ は $p \leq \sqrt{x}$ を満たす素因子 $p$ をもつ」

合成数xが素数かどうかはルートxまでの値で割れるかどうか見ればいいということ。

xの値まで調べるとするとO(x)となる。

でもxの半分まで調べればいいんじゃない?と気がつくと。O(x/2)

ルートのことに気がつくとO( $p \leq \sqrt{x}$ )という風に処理が速くなるぞ。

普段、素数判定なんて、もちろんしないが、処理速度の意識はしたい。

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とその約数が答えなのだ。