C 練習例16 - 最大公約数と最小公倍数

C 语言经典100例C言語の定番100例

問題: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例C言語の定番100例

その他の拡張