C Exercise Examples 16-- greatest common divisor and least common multiple
100 cases of classic C language
Title: Enter two positive integers m and n, seeking the greatest common divisor and least common multiple.
Program analysis:
(1) Product = least common multiple of two numbers entered in addition to their common denominator, the key is to find the common denominator;
(2) greatest common divisor using Euclidean algorithm (also known as Euclidean algorithm)
1) Proof: Let c is the greatest common divisor of a and b, denoted by c = gcd (a, b), a> = b,
So r = a mod b
Let a = kc, b = jc, then k, j are relatively prime, otherwise c is not the greatest common divisor
According to the, r = a-mb = kc-mjc = (k-mj) c
R c is seen multiples, and k-mj and j are relatively prime, otherwise the aforementioned k, j coprime contradiction,
It can be seen, b and r is the greatest common divisor c, ie, gcd (a, b) = gcd (b, a mod b), proved.
2) algorithm description:
The first step: a ÷ b, so that r is a remainder (0≤r Step two: Swap: set a ← b, b ← r, and returns the first step.
Source Code:
// Created by www.w3big.com on 15/11/9. // Copyright © 2015年 本教程. All rights reserved. // #include<stdio.h> int main() { int a,b,t,r; printf("请输入两个数字:\n"); scanf("%d %d",&a,&b); if(a<b) {t=b;b=a;a=t;} r=a%b; int n=a*b; while(r!=0) { a=b; b=r; r=a%b; } printf("这两个数的最大公约数是%d,最小公倍数是%d\n",b,n/b); return 0; }
The above example output is:
请输入两个数字: 12 26 这两个数的最大公约数是2,最小公倍数是156