$m,n\ge1$の最大公約数を$\gcd(m,n)$と表します。
このとき、$\gcd(m,n)$は次の漸化式で計算することができます。
$\beginend{cases}{
\gcd(m,m) &= m \\
\gcd(m,n) &= \gcd(n,m) = \gcd(m-n,n) &(m>n)
}$
2行目は次の様にできます。
$\gcd(m,n) = \gcd(|m-n|,\min(m,n)) \quad(m\ne n)$
$g \coloneqq \gcd(m,n)$
$ga \coloneqq m, gb \coloneqq n$
$a,b$は互いに素。
$\Longrightarrow a-b,b$は互いに素。
$\gcd(m-n,n) = \gcd(g(a-b),gb) = g\gcd(a-b,b) = g$
プログラム上で最大公約数の表が必要な場合、
ユークリッドの互除法で一つずつ求めるよりも
この漸化式を使った方が効率的です。
$\color{gray}8$ | $\color{red}8$ | |||||||
$\color{gray}7$ | $\color{red}7$ | |||||||
$\color{gray}6$ | $\color{red}6$ | |||||||
$\color{gray}5$ | $\color{red}5$ | |||||||
$\color{gray}4$ | $\color{red}4$ | |||||||
$\color{gray}3$ | $\color{red}3$ | |||||||
$\color{gray}2$ | $\color{red}2$ | |||||||
$\color{gray}1$ | $\color{red}1$ | |||||||
$\slfrac nm$ | $\color{gray}1$ | $\color{gray}2$ | $\color{gray}3$ | $\color{gray}4$ | $\color{gray}5$ | $\color{gray}6$ | $\color{gray}7$ | $\color{gray}8$ |
$\color{gray}4$ | $4$ | |||
$\color{gray}3$ | $3$ | |||
$\color{gray}2$ | $\color{red}1$ | $2$ | ||
$\color{gray}1$ | $\clone1\quad$ | $\color{red}1$ | ||
$\slfrac nm$ | $\color{gray}1$ | $\color{gray}2$ | $\color{gray}3$ | $\color{gray}4$ |
$\color{gray}4$ | $4$ | |||
$\color{gray}3$ | $\color{red}1$ | $\color{red}1$ | $3$ | |
$\color{gray}2$ | $\clone1\quad$ | $\clone\quad2$ | $\color{red}1$ | |
$\color{gray}1$ | $1$ | $\clone1\quad$ | $\color{red}1$ | |
$\slfrac nm$ | $\color{gray}1$ | $\color{gray}2$ | $\color{gray}3$ | $\color{gray}4$ |
$\color{gray}4$ | $\color{red}1$ | $\color{red}2$ | $\color{red}1$ | $4$ |
$\color{gray}3$ | $\clone1\quad$ | $\clone\quad1$ | $\clone\quad3$ | $\color{red}1$ |
$\color{gray}2$ | $1$ | $\clone2\quad$ | $\clone\quad1$ | $\color{red}2$ |
$\color{gray}1$ | $1$ | $1$ | $\clone1\quad$ | $\color{red}1$ |
$\slfrac nm$ | $\color{gray}1$ | $\color{gray}2$ | $\color{gray}3$ | $\color{gray}4$ |
$\color{gray}8$ | $1$ | $2$ | $1$ | $4$ | $1$ | $4$ | $1$ | $8$ |
$\color{gray}7$ | $1$ | $1$ | $1$ | $1$ | $1$ | $1$ | $7$ | $1$ |
$\color{gray}6$ | $1$ | $2$ | $3$ | $2$ | $1$ | $6$ | $1$ | $2$ |
$\color{gray}5$ | $1$ | $1$ | $1$ | $1$ | $5$ | $1$ | $1$ | $1$ |
$\color{gray}4$ | $1$ | $2$ | $1$ | $4$ | $1$ | $2$ | $1$ | $4$ |
$\color{gray}3$ | $1$ | $1$ | $3$ | $1$ | $1$ | $3$ | $1$ | $1$ |
$\color{gray}2$ | $1$ | $2$ | $1$ | $2$ | $1$ | $2$ | $1$ | $2$ |
$\color{gray}1$ | $1$ | $1$ | $1$ | $1$ | $1$ | $1$ | $1$ | $1$ |
$\slfrac nm$ | $\color{gray}1$ | $\color{gray}2$ | $\color{gray}3$ | $\color{gray}4$ | $\color{gray}5$ | $\color{gray}6$ | $\color{gray}7$ | $\color{gray}8$ |
四則演算すら使わず転写だけで表が出来ました。