Bagaimana untuk mencari pembahagi sepunya terbesar dalam bahasa C

Kaedah pelaksanaan mencari pembahagi sepunya terhebat dalam bahasa C memerlukan contoh kod khusus

Pembahagi sepunya terbesar, dirujuk sebagai faktor sepunya terbesar, merujuk kepada nilai maksimum antara pembahagi yang dikongsi oleh dua atau lebih integer. Dalam reka bentuk algoritma, mencari pembahagi sepunya terbesar adalah masalah biasa. Berikut akan memperkenalkan secara terperinci beberapa kaedah untuk melaksanakan pembahagi sepunya terbesar dalam bahasa C dan memberikan contoh kod khusus.

Kaedah 1: Kaedah brute force
Kaedah brute force ialah kaedah yang mudah dan langsung, dengan melintasi semua pembahagi yang mungkin dan kemudian mencari pembahagi terbesar sebagai pembahagi sepunya terbesar.

#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;
}

Kaedah 2: Pembahagian Euclidean
Pembahagian Euclidean (juga dikenali sebagai algoritma Euclidean) adalah berdasarkan prinsip matematik mudah: pembahagi sepunya terbesar bagi dua integer adalah sama dengan pembahagi sepunya terbesar bagi nombor yang lebih kecil dan perbezaan antara kedua-dua nombor.

#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;
}

Kaedah 3: Kaedah penolakan lebih fasa
Kaedah penolakan lebih fasa juga merupakan kaedah yang lebih biasa digunakan untuk mencari pembahagi sepunya terbesar Ia memperoleh perbezaan antara dua nombor dengan menolaknya secara berterusan, dan kemudian mencari pembahagi sepunya terbesar daripada perbezaan sehingga dua nombor Nombor adalah sama.

#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;
}

Di atas adalah tiga cara biasa untuk melaksanakan penyebut sepunya terbesar dalam bahasa C Melalui idea algoritma yang berbeza, kita boleh memilih kaedah yang sesuai untuk diselesaikan dalam senario yang berbeza, dan memilih pelaksanaan kod yang sepadan mengikut keperluan khusus.

Atas ialah kandungan terperinci Bagaimana untuk mencari pembahagi sepunya terbesar dalam bahasa C. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!