Solve the greatest common divisor and the least common multiple

Catalog

Find the greatest common divisor

1. Violent solution

 2. division  

Find the least common multiple  

1. Violent solution

2. The greatest common divisor method  

---

Find the greatest common divisor

  Definition of the greatest common divisor ： If there is a natural number a Can be Natural number b to be divisible by , said a by b Multiple ,b by a The divisor of . The common divisor of several natural numbers , It's called the common divisor of these natural numbers . The greatest common divisor of the common divisor , It is called the greatest common divisor of these natural numbers . example ： stay 2、4、6 in ,2 Namely 2,4,6 Maximum common divisor of .

  Knowing the definition of the greatest common divisor , Let's learn how to solve the greatest common divisor .

1. Violent solution

  Ideas ： Suppose there are two numbers m and n, First find the smaller of the two numbers min, And then use it while Loop to find out m and n Maximum common divisor of .while The cycle body of the cycle is if m and n to be divisible by min Zero at the same time , So the min Namely m and n Maximum common divisor of ; If this condition is not met min Self subtraction one .

Code implementation ：

#include <stdio.h>
int main()
{
	int m, n;
	printf(" Please enter two integers :>");
	scanf("%d %d", &m, &n);
	int min = (m < n ? m : n);
	while (1)
	{
		if ((m % min == 0) && (n % min == 0))
		{
			break;
		}
		min--;
	}
	printf("%d and %d The greatest common divisor of %d\n", m, n, min);
	return 0;
}

Output results ： 

 2. division  

  division , also called Euclidean algorithm (Euclidean algorithm), Is to ask for two Positive integer Algorithm of the greatest common divisor of . It is the oldest algorithm known , It dates back to... BC 300 Years ago . Its concrete method is ： Divide the larger number by the smaller number , And then the remainder that appears （ The first remainder ） Remove divisor , And then the remainder that appears （ Second remainder ） Remove the first remainder , So again and again , Until the end, the remainder is 0 until . If you want to find the greatest common divisor of two numbers , So the final divisor is the greatest common divisor of these two numbers .

Code implementation ：

#include <stdio.h>
int main()
{
	int m, n;
	printf(" Please enter two integers :>");
	scanf("%d %d", &m, &n);
	int m1 = m;
	int n1 = n;// preservation m and n The data of 
	int r = 0;
	while (r = m % n)
	{
		m = n;
		n = r;
	}
	printf("%d and %d The greatest common divisor of %d\n", m1, n1, n);
	return 0;
}

  Output results ：

Find the least common multiple  

    Definition of least common multiple ： If a number is both a again b Multiple , Then let's call this number a and b The common multiple of , If this number is in a b Is the smallest of all common multiples of , Then this number is the least common multiple . for example ,10 and 20 The minimum common multiple of is 20.

1. Violent solution

  Suppose there are two numbers m and n, First find the maximum of the two numbers max, And then use it while Loop to find out m and n The least common multiple of .while The cycle body of the cycle is if max to be divisible by m and n Zero at the same time , So the max Namely m and n The least common multiple of ; If this condition is not met max Self plus one .

Code implementation ：

#include <stdio.h>
int main()
{
	int m, n;
	printf(" Please enter two numbers :>");
	scanf("%d %d", &m, &n);
	int max = (m > n ? m : n);
	while (1)
	{
		if ((max % m == 0) && (max % n == 0))
		{
			break;
		}
	}
	printf("%d and %d The minimum common multiple of is %d\n", m, n, max);
	return 0;
}

Output results ： 

2. The greatest common divisor method  

  Suppose there are two numbers m and n, And m and n The greatest common divisor of is x、 Minimum common multiple y, Then there is a relationship between the least common multiple and the greatest common divisor ：m * n = x * y. For example, this relation , We can implement our code .

Code implementation ：

#include <stdio.h>
int main()
{
	int m, n;
	printf(" Please enter two numbers :>");
	scanf("%d %d", &m, &n);
	int m1 = m;
	int n1 = n;
	int r = 0;
	while (r = m % n)
	{
		m = n;
		n = r;
	}
	printf("%d and %d The minimum common multiple of is %d\n", m1, n1, m1 * n1 / n);

}

Output results ： 

  This blog mainly introduces two common methods of the greatest common divisor and least common multiple . If you are still interested in other methods , You can search for , I won't repeat it here . Last , If you think you've got something , You can point a favor to support ！