Shulou(Shulou.com)06/02 Report--

This article mainly introduces the C language to achieve the maximum common divisor of which methods, the article is very detailed, has a certain reference value, interested friends must read it!

Topic description

Find the maximum common divisor of any two positive integers

Analysis of problems

The greatest common factor, also known as the greatest common divisor, refers to the largest of the divisors shared by two or more integers. Similarly, the greatest common divisor of arecine b is denoted as (arecine b), and the greatest common divisor of several integers also has the same sign. There are many methods to find the maximum common divisor, such as prime factor decomposition, short division, tossing and turning division and more phase reduction method. The concept corresponding to the greatest common divisor is the least common multiple, and the least common multiple of ameme b is denoted by [aforce b].

Baidu encyclopedia

There are many ways to find the maximum common divisor. In this paper, I will use exhaustive method, division method and subtraction method to find the maximum common divisor of two positive integers (the maximum common factor).

Code implementation method 1: exhaustive method

The exhaustive method (enumeration method) is the simplest and most intuitive method.

The specific steps are as follows: first find the minimum value min of two numbers (the maximum common divisor must be less than or equal to the minimum value of two numbers), then decrease traversal from the minimum value min (loop end condition is I > 0), if you encounter a number that is the factor of both integers, then exit traversal using break (exit loop), then the ergodic value I is the maximum common divisor of two positive integers.

# include / * @ brief get the maximum common factor of two positive integers (exhaustive method) * @ param num1 first positive integer * @ param num2 second positive integer * @ return largest common factor * / int Get_Max_Comm_Divisor (int num1, int num2) {int I = 0; / / get the minimum value of two integers int min = num1

) {/ / I is the common multiple of num1 and num2 if (num1% I = = 0 & & num2% I = = 0) break;} return I;} int main () {int num1 = 0, num2 = 0; puts ("Please enter two positive integers."); scanf ("% d% d", & num1, & num2) Printf ("greatest common divisor is% d.\ n", Get_Max_Comm_Divisor (num1, num2)); return 0;}

Running result

Method 2: toss and turn division

Toss and turn division, also known as Euclidean algorithm, refers to the maximum common divisor used to calculate two non-negative integers a _ r _ b. There are two aspects in the application field: mathematics and computer. The formula gcd (a mod b) = gcd (b).

. Euclid algorithm is an algorithm used to find the maximum common divisor of two positive integers. The ancient Greek mathematician Euclid first described this algorithm in his book The Elements, so it was named Euclid algorithm.

Extended Euclid algorithm can be used in RSA encryption and other fields.

For example:

If you need to ask for the greatest common divisor of two positive integers, using the Euclid algorithm, it goes like this:

1997 / 615 = 3 (remaining 152)

615 / 152 = 4 (remaining 7)

152 / 7 = 21 (remaining 5)

7 / 5 = 1 (remaining 2)

5 / 2 = 2 (remaining 1)

2 / 1 = 2 (remainder 0)

So far, the maximum common divisor is 1.

The division operation is done repeatedly with the divisor and the remainder. When the remainder is 0, the divisor of the current formula is taken as the maximum common divisor, so the maximum common divisor of 1997 and 615 is obtained.

Baidu encyclopedia

Math low achiever's I think this little algorithm is particularly magical, but I don't want to study it in depth (why can I use division by toss and turn to find the greatest common factor?). If you want to prove it, you can try to prove it by yourself, I will directly choose to memorize it. Heh heh.

Although the algorithm is difficult to understand, the implementation process is not difficult, according to the concept of division, can be converted into code.

Specific steps: first find the remainder remainder of two numbers num1 and num2. Then assign num2 to num1, and let the divisor num2 of the last remainder be the divisor of the next remainder. At the same time, the current remainder remainder is used as the divisor of the next remainder. This goes on and on until the remainder is zero, where the divisor num2 is the largest common factor we require.

At first, there is no need to distinguish the size of the two numbers, because if num1 is smaller than num2, then the result of the remainder is still num1, so the next remainder becomes num2% num1, that is, the large value is on the left, as the divisor).

# include / * @ brief gets the greatest common factor of two positive integers (division) * @ param num1 first positive integer * @ param num2 second positive integer * @ return largest common factor * / int Get_Max_Comm_Divisor (int num1, int num2) {int remainder = num1% num2; / / remainder while (remainder! = 0) {num1 = num2 / / update divisor num2 = remainder; / / update divisor remainder = num1% num2; / / update remainder} return num2; / / the final divisor is the maximum common factor} int main () {int num1 = 0, num2 = 0; puts ("Please enter two positive integers."); scanf ("% d% d", & num1, & num2) Printf ("greatest common divisor is% d.\ n", Get_Max_Comm_Divisor (num1, num2)); return 0;}

Running result

Method 3: more subtractive method

"Nine chapters arithmetic" is a mathematical monograph in ancient China, in which "more relative subtraction" can be used to find the maximum common divisor of two numbers.

Can be half half, not half, the number of sub-denominator, son, in order to reduce more, more derogation, and so on. Let's make an equal number.

Vernacular translation:

(if you need to make an appointment about the score, then) if you can cut it in half, you can cut it in half (that is, you can cut it by 2). If it cannot be halved, then compare the size of the denominator and the numerator, subtract the decimal from the large number, subtract from each other until the subtraction is equal to the difference, and use this equal number to divide.

Baidu encyclopedia

There is also a method called toss and turn subtraction, which seems to be the same as the more subtractive method, or at least the same principle.

The method of subtraction (seeking the maximum common divisor), that is, Nicomanchez method, is characterized by a series of subtraction to obtain the maximum common divisor. For example: two natural numbers 35 and 14, subtract decimals with large numbers, (35, 14)-> (21, 14)-> (7, 14), at this time, 7 is less than 14, make an exchange, take 14 as a subtraction, that is, (14)-> (7, 7), subtract again, and the result is 0, so the maximum common divisor 7 is obtained.

Baidu encyclopedia

I was surprised by the division just now, but I didn't think of a way to subtract it. However, it is still the old rule to implement this method directly in code without proving it.

Different from the division method of tossing and turning, the subtraction method needs to consider the size of two numbers, which can only be subtracted by large numbers and small ones.

Implementation steps: first find the difference diff of two positive integers num1 and num2, and then assign num2 to num1, so that the subtraction num2 of the last subtraction is used as the subtraction of the next subtraction. At the same time, the current difference diff is used as the subtraction next time. This keeps subtracting until the difference is zero, where the divisor num2 is the largest common factor we require.

# include / * @ brief gets the maximum common factor of two positive integers (more subtractive method) * @ param num1 first positive integer * @ param num2 second positive integer * @ return largest common factor * / int Get_Max_Comm_Divisor (int num1, int num2) {/ / the result of subtracting (taking positive values) int diff = num1 > num2? Num1-num2: num2-num1; while (diff! = 0) {num1 = num2; / / Update minus num2 = diff; / / Update minus diff = num1 > num2? Num1-num2\: num2-num1; / / update the result of subtraction between two numbers (take positive values)} return num2; / / the final subtraction is the maximum common factor} int main () {int num1 = 0, num2 = 0; puts ("Please enter two positive integers."); scanf ("% d% d", & num1, & num2) Printf ("greatest common divisor is% d.\ n", Get_Max_Comm_Divisor (num1, num2)); return 0;}

Running result

These are all the contents of the article "what are the ways to find the greatest common divisor in C language?" Thank you for your reading! Hope to share the content to help you, more related knowledge, welcome to follow the industry information channel!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.