greatest common divisor

List of articles

【C Language – The road of big men 】

---

---

1. What is a common divisor ？

Common divisor , Also known as “ The common factor ”. It is a number that can divide several integers at the same time . If an integer is several integers at the same time Divisor , Call this integer their “ Common divisor ”.

2. greatest common divisor

The largest of the common divisors is called the greatest common divisor . For any number of positive integers ,1 Their common factor is always . The common divisor is opposite to the common multiple , Is both A The divisor of is also B The divisor of ,12 and 15 The common divisor of is 1,3, The greatest common divisor is 3. Another example ,30 and 40, Their common divisors are 1,2,5,10, The greatest common divisor is 10

3. The relationship between the greatest common divisor and the least common multiple ：

The product of two numbers / greatest common divisor = Minimum common multiple

4. Problem solving guidance

Such as 18 and 6, We can know that the greatest common divisor of two numbers must be less than or equal to the smallest one , Then to achieve the greatest common divisor , You must first find the smallest of the two numbers
And then from 6 Or ratio 6 Find the least common divisor among small numbers

5. Code display ：

The code is as follows （ Example ）：

#include<stdio.h>
int main() {
    
	
	int m = 0;
	int n = 0;
	scanf("%d %d", &m, &n);
	int min = (m < n ? m : n);
	while (1)
	{
    
		if (m % min == 0 && n % min == 0)
		{
    
			printf("%d", min);
			break;
		}
		min--;
	}
	return 0;
}

Of course, there is more than one method , This method is inefficient

6. division

The introduction is shown in the figure ：

Pictured , use 24 except 18 Take the remainder 6
use 18 except 6 Take remainder as 0
6 Is the greatest common divisor of these two numbers
As shown in the figure above, if we put 24 regard as m, hold 18 regard as n, If the remainder is not 0, will n The value is assigned to m, The value of the remainder is assigned to n
Remainder if yes 0,n Is the greatest common divisor

7. Code demonstration ：

#include<stdio.h>// greatest common divisor 
int main() {
    

	int m = 0;
	int n = 0;
	int r = 0;
	scanf("%d %d", &m, &n);
	while (r = m % n)
	{
    
		m = n;
		n = r;
	}
	printf("%d", n);
	return 0;
}

summary

The contents involved here are quite basic , If you don't know some syntax in the above code , It shows that the foundation is too weak
You can read my series of articles 【C】 C Introduction to language
Of course, as long as you have a clear idea , This kind of code is still very easy to write .