ユークリッドの互除法
Euclidean algorithm
2つの自然数の
最大公約数
を得るアルゴリズム
試し割り法
を用いるより効率的
a > b
を仮定できる
a < b
でも
small % large = small
になっていて入れ替わってくれる
変数の値の入れ替え
に
tmp
を噛ませなくていいのが楽
あんも.icon
code:jl
function gcd(a::T, b::T) where T<:Integer
while b != 0
a, b = b, rem(a, b)
end
return abs(a)
end
拡張互除法
整数解が得られる