C Exercise Example 16 - Greatest Common Divisor and Least Common Multiple

Title:Input two positive integers m and n, and find their greatest common divisor and least common multiple.

Program analysis:

(1) Least common multiple = the product of the two input numbers divided by their greatest common divisor; the key is to find the greatest common divisor.

(2) Use the Euclidean algorithm (also known as the Euclidean algorithm) to find the greatest common divisor.

1) Proof: Let c be the greatest common divisor of a and b, denoted as c = gcd(a, b), a >= b.
Let r=a mod b
Let a = kc, b = jc, then k and j are coprime; otherwise c would not be the greatest common divisor.
From the above, r=a-mb=kc-mjc=(k-mj)c
It can be seen that r is also a multiple of c, and k - mj and j are coprime; otherwise it contradicts the previous fact that k and j are coprime.
Thus, it can be seen that the greatest common divisor of b and r is also c, i.e., gcd(a,b)=gcd(b,a mod b). Proved.

2) Algorithm Description:

Step 1: a ÷ b, let r be the resulting remainder (0 ≤ rStep 2: Swap: set a←b, b←r, and return to step 1.

Example

// Created by www.example.com on 15/11/9. // Copyright © 2015 Example. All rights reserved. // #include<stdio.h> int main() { int a,b,t,r,n; printf("Please enter two numbers:\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("The greatest common divisor of these two numbers is %d, and the least common multiple is %d\n",b,n/b); return 0; }

The output of the above example is:

请输入两个数字：
12 26
这两个数的最大公约数是2，最小公倍数是156

100 Classic C Examples

other extensions