How to find the greatest common divisor in C language

The implementation method of finding the greatest common divisor in C language requires specific code examples

The greatest common divisor, referred to as the greatest common factor, refers to two or more integers The maximum value among the common divisors. In algorithm design, finding the greatest common divisor is a common problem. The following will introduce in detail several methods of implementing the greatest common divisor in C language and provide specific code examples.

Method 1: Brute force method
The brute force method is a simple and direct method, by traversing all possible divisors and then finding the largest divisor as the greatest common divisor.

#include <stdio.h>

int gcd(int a, int b) {
    int i, result = 1;

    for(i = 1; i <= a && i <= b; i++) {
        if(a % i == 0 && b % i == 0) {
            result = i;
        }
    }

    return result;
}

int main() {
    int a, b;

    printf("请输入两个整数：
");
    scanf("%d%d", &a, &b);

    printf("最大公约数为：%d
", gcd(a, b));

    return 0;
}

Method 2: Euclidean division method
Euclidean division method (also known as Euclidean algorithm) is based on a simple mathematical principle: the greatest common divisor of two integers is equal to the smaller number and the two numbers. The greatest common divisor of the differences.

#include <stdio.h>

int gcd(int a, int b) {
    int remainder;

    while(b != 0) {
        remainder = a % b;
        a = b;
        b = remainder;
    }

    return a;
}

int main() {
    int a, b;

    printf("请输入两个整数：
");
    scanf("%d%d", &a, &b);

    printf("最大公约数为：%d
", gcd(a, b));

    return 0;
}

Method 3: More phase subtraction method
The more phase subtraction method is also a more commonly used method to find the greatest common divisor. It obtains the difference between two numbers by continuously subtracting them, and then finds the difference. Greatest common divisor until two numbers are equal.

#include <stdio.h>

int gcd(int a, int b) {
    while(a != b) {
        if(a > b) {
            a = a - b;
        } else {
            b = b - a;
        }
    }

    return a;
}

int main() {
    int a, b;

    printf("请输入两个整数：
");
    scanf("%d%d", &a, &b);

    printf("最大公约数为：%d
", gcd(a, b));

    return 0;
}

The above are three common methods for realizing the greatest common divisor in C language. Through different algorithm ideas, we can choose the appropriate method to solve in different scenarios, and select the corresponding code according to specific needs. accomplish.

The above is the detailed content of How to find the greatest common divisor in C language. For more information, please follow other related articles on the PHP Chinese website!