プログラマたるものアルゴリズムとデータ構造は知っていて当然の知識です。しかし、教科書的な知識しか知らなくて、実践的なプログラミングに役立てることができるでしょうか(編集部) 最大公約数を求める 「最大公約数を求めるプログラムを作って」といわれて、すぐに書けるでしょうか。 一般的には小学校で最大公約数の求め方を教わります。2つの数を共通する素数で割っていくというものです。そのままプログラムしようとすると、まず素数を求めるところから始めなければならず、少々難しそうです。 最も単純にやるとすれば、2つの数の小さいほうから1ずつ減らして両方の数を割っていき、どちらも余りが0になるものを求めるという方法でよいでしょう。しかしこのやり方は無駄が多そうです。 「ユークリッドの互除法」という方法を使うと簡単にプログラムにすることができます。ユークリッドの互除法とは以下のような方法で最大公約数を求めるやり方