Aizu Online Judge(AOJ)の過去問から、その提出コードの解答例です。
2つの自然数 x, y を入力とし、それらの最大公約数を求めるプログラムです。
・問題
2つの自然数 x, y を入力とし、それらの最大公約数を求めるプログラムを作成してください。
2つの整数 x と y について、x ÷ d と y ÷ d の余りがともに 0 となる d のうち最大のものを、x と y の最大公約数(Greatest Common Divisor)と言います。
例えば、35 と14 の最大公約数 gcd (35, 14) は 7 となります。
これは、35 の約数{1, 5, 7, 35}、14 の約数 {1, 2, 7, 14} の公約数 {1, 7} の最大値となります。
・入力される値
x と y が1つの空白区切りで1行に与えられます。
・期待する出力
最大公約数を1行に出力してください。
・条件
僕が作成、提出したコードは、以下のとおりです。
/* ALDS1_1_B Greatest Common Divisor http://judge.u-aizu.ac.jp/ 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<stdio.h> int gcd(int x,int y){ if(x<y){ int tmp; tmp=y; y=x; x=tmp; } while(y>0){ int r; r=x%y; x=y; y=r; } return x; } int main(void){ int x,y; scanf("%d %d",&x,&y); printf("%d\n",gcd(x,y)); return 0; }
設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge(AOJ)」です。
http://judge.u-aizu.ac.jp/onlinejudge/
ALDS1_1_B Greatest Common Divisor