1, Least common multiple (LCM)

Minimum common multiple = the product of the two input numbers is divided by their maximum common divisor (a*b / maximum common divisor). The key is to find the maximum common divisor;

2, Maximum common divisor (GCD)

1. Rolling division / Euclidean algorithm

Definition: first divide the larger number by the smaller number to calculate the remainder. Then divide the remainder by the divisor to find the new remainder. Then divide the divisor by the remainder... Keep cycling... Until the remainder is 0, and finally b is the maximum common divisor. Example (a=1997, b=615):

a	b	a mod b
1997	615	152	1997/615=3...152
615	152	7	615/152=4...7
152	7	5	152/7=21...5
7	5	2	7/5=1...2
5	2	1	5/2=2...1
2	1	0	2/1=2...0

1.1 general

#include<stdio.h>
int main(){
	int a,b;
	printf("Please enter a,b Value of:");
	scanf("%d %d",&a,&b);
	if(a<b){  //Swap the size of a and b 
		int temp = b;
		b = a;
		a = temp;
	}
	int r;  //r stands for remainder
	r = a%b;
	int n;
	n = a*b; //The least common multiple is a*b/GCD 
	while(r!=0){
		a = b;
		b = r;
		r = a%b;
	}
	printf("The greatest common divisor is%d,The least common multiple is%d",b,n/b);
	return 0;
}

1.2 recursion

#include<stdio.h>
//Recursive implementation of maximum common divisor 
int gcd(int a,int b){
	if(a%b == 0)
		return b;
	else
		return gcd(b,a%b);
}
int main(){
	int a,b;
	printf("Please enter a,b Value of:");
	scanf("%d %d",&a,&b);
	if(a<b){  //Swap the size of a, b 
		int temp = b;
		b = a;
		a = temp;
	}
	int n;
	n = a*b; //The least common multiple is a*b/GCD 
	printf("The greatest common divisor is%d,The least common multiple is%d",gcd(a,b),n/gcd(a,b));
	return 0;
}

2. Modified subtraction

The method of more relative derogation comes from the nine chapters of arithmetic: "if it can be half, it can be half. If it can not be half, the number of denominators and children shall be set, so as to reduce more from less, and reduce more from more, so as to seek its equal. It shall be approximated by the equal number."
Specific methods:
Step 1: arbitrarily give two positive integers; If they are all 2 even numbers, use 2 reduction; Otherwise, proceed to step 2.
Step 2: the large number between the two numbers is the reduced number. Then, compare the difference with the smaller number, and subtract the decimal from the large number until the subtraction is the same as the difference. At this time, the difference is the maximum common divisor between the two numbers.
Step 3: the difference obtained and the opportunity of about 2 is the greatest common divisor
Example (a=12,b=6)
Step 1: reduce to 6,3 (reduce by 1 time);
Step 2:

a	b	a-b
6	3	6-3=3

Step 3: 3 * 2 = 6 (gcd);

2.1 general

#include<stdio.h>
int main(){
	int a,b;
	int x;       //Difference between two numbers
	printf("Please enter a,b Value of:");
	scanf("%d %d",&a,&b);
	int n = a*b; //Product of two numbers
	int i=0;     //Record the number of approximately 2
	while(a%2==0 && b%2==0){
		a/=2;
		b/=2;
		i++;
	}
	if(a<b){
		int temp=b;
		b = a;
		a = temp;
	}
	x = a-b;
	while(x!=b){
		a = x>b?x:b;
		b = x<b?x:b;
		x = a-b;
	}
	if(i==0) 
		printf("The maximum common divisor is%d,The least common multiple is%d",x,n/x);
	else{
		for(int j=0; j<i; j++){
			x = x*2;
		}
		printf("The maximum common divisor is%d,The least common multiple is%d",x,n/x);
	}
	return 0;
}

2.2 recursion

#include<stdio.h>
//recursion 
int gcd(int a,int b){
	if(b == a-b) 
		return b;
	else
		return gcd(a-b>b?a-b:b,a-b<b?a-b:b);
} 
int main(){
	int a,b;
	printf("Please enter a,b Value of:");
	scanf("%d %d",&a,&b);
	int n = a*b; //Product of two numbers
	int i=0;     //Record the number of approximately 2
	while(a%2==0 && b%2==0){
		a/=2;
		b/=2;
		i++;
	}
	if(a<b){
		int temp=b;
		b = a;
		a = temp;
	}
	if(i==0) 
		printf("The maximum common divisor is%d,The least common multiple is%d",gcd(a,b),n/gcd(a,b));
	else{
		int x = gcd(a,b);
		for(int j=0; j<i; j++){
			x = x*2;
		}
		printf("The maximum common divisor is%d,The least common multiple is%d",x,n/x);
	}
	return 0;
}

3. Exhaustion / Violence Act

[maximum common divisor]: for two different positive integers a and b, there are numbers in [1,min{a,b}] that can be divided by a and b at the same time, and the largest number is the maximum common divisor.
[least common multiple]: for two different positive integers a and b, starting from max{a,b}, the first number found that can divide a and b is the least common multiple.

#include<stdio.h>
//Exhaustive realization of maximum common factor 
int gcd(int a,int b){
	int temp;
	int max=1; //The largest of the common factors 
	if(a<b){
		temp = a;
		a = b;
		b = temp;
	}
	for(int i=1; i<=b; i++){
		if(a%i==0 && b%i==0)
			max = i;
	}
	return max;
}

//Exhaustive realization of least common multiple
int lcm(int a,int b){
	int max;  //The larger of a and b
	max = a>b?a:b;
	int i;
	for(i=max; ; i++){
		if(i%a==0 && i%b==0)
			break;
	}
	return i; 
} 

int main(){
	int a,b;
	printf("Please enter a,b Value of:");
	scanf("%d %d",&a,&b);
	printf("The maximum common divisor is%d,The least common multiple is%d",gcd(a,b),lcm(a,b));
}