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

This article mainly introduces "C language how to find the greatest common divisor of two positive integers", in daily operation, I believe many people in C language how to find the greatest common divisor of two positive integers on the question of doubt, Xiaobian consulted all kinds of information, sorted out simple and easy to use operation methods, hope to answer "C language how to find the greatest common divisor of two positive integers" doubts helpful! Next, please follow the small series to learn together!

preface

The greatest Common Divisor (GCD) of two positive integers is the largest integer that divides them exactly. There are many ways to find the greatest common divisor of two positive integers. Three methods are introduced in detail in this paper: exhaustive method, Euclid algorithm (division method) and recursive method.

We start with a problem: Write a function Gcd() that calculates the greatest common divisor, and call it in the main function to calculate and output the greatest common divisor arbitrarily input from the keyboard.

1. exhaustive method

According to the definition of the greatest common divisor, we can use the simplest method to write code-exhaustive method. Since the greatest common divisor of a and b cannot be greater than the lesser of a and b, otherwise it must not be divisible, so first find t, the lesser of a and b, and then try every possibility by subtracting 1 from t, i.e., test all integers between t and 1. The first t that satisfies the common divisor condition is the greatest common divisor of a and b. We can write the function Gcd() as follows:

//Function function: calculate the greatest common divisor of a and b, and return-1int Gcd(int a, int b){ int i, t; if (a

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.