ユークリッドの互除法

2つの自然数の最大公約数を求めるには、ユークリッドの互除法というアルゴリズムを使うといい。

最大公約数の算出 | WEBサービス創造記
C言語入門 - 入力した2つの自然数の最大公約数を求める - Webkaru

実は2種類あって、減算を使う方法は、

剰余を使う方法は、

と書く。

mainは、

と書く。

$ vi euclidean_algorithm.c 
$ gcc euclidean_algorithm.c -o euclidean_algorithm
$ ./euclidean_algorithm 
a: 72
b: 128
result1 = 8
result2 = 8
$ euclidean_algorithm_1

このように最大公約数を求めることができる。

Sample/algorithm/euclidean_algorithm/euclidean_algorithm/src/euclidean_algorithm at master · bg1bgst333/Sample · GitHub