C 練習例16 - 最大公約数と最小公倍数
問題:2つの正の整数mとnを入力し、その最大公約数と最小公倍数を求めます。
プログラム分析:
(1)最小公倍数 = 入力した2つの数の積をそれらの最大公約数で割ったものです。鍵となるのは最大公約数を求めることです;
(2)最大公約数を求めるには、ユークリッドの互除法(別名ユークリッドアルゴリズム)を使用します
1)証明:cをaとbの最大公約数とし、c=gcd(a,b)と表す。a>=b、
r=a mod bとする
a=kc、b=jcとすると、kとjは互いに素である。そうでなければcは最大公約数ではない
上記より、r=a-mb=kc-mjc=(k-mj)c
rもcの倍数であり、かつk-mjとjは互いに素である。そうでなければ前述のk、jが互いに素であることと矛盾する。
これにより、bとrの最大公約数もcであることが分かる。すなわちgcd(a,b)=gcd(b,a mod b)が証明された。
2)アルゴリズムの説明:
第一步:a ÷ b、rをその余りとする(0≤r第二步:交換:a←b、b←rとし、第一步に戻る。
実例
// Created by www.example.com on 15/11/9.
// Copyright © 2015年 サンプル. All rights reserved.
//
#include<stdio.h>
int main()
{
int a,b,t,r,n;
printf("2つの数字を入力してください:\n");
scanf("%d %d",&a,&b);
if(a<b)
{t=b;b=a;a=t;}
r=a%b;
n=a*b;
while(r!=0)
{
a=b;
b=r;
r=a%b;
}
printf("この2つの数の最大公約数は%d、最小公倍数は%d\n",b,n/b);
return 0;
}
上記の実例の出力結果は次のとおりです:
请输入两个数字: 12 26 这两个数的最大公约数是2,最小公倍数是156その他の拡張
C言語の定番100例