C //习题 7.1 写两个函数，分别求两个整数的最大公约数和最小公倍数，用主函数调用这两个函数，并输出结果。两个整数由键盘输入。

C程序设计 （第四版） 谭浩强 习题7.1

习题 7.1 写两个函数，分别求两个整数的最大公约数和最小公倍数，用主函数调用这两个函数，并输出结果。两个整数由键盘输入。

IDE工具：VS2010

Note: 使用不同的IDE工具可能有部分差异。

 

代码块

方法1：

#include <>
#include <>

int sum;                                          //定义外部变量sum

//最大公约数函数
int HCF(int x, int y){
    int i, k, m, n;
    sum = 1;
    k = x > y ? y : x;
    i = 2;
    while (i <= k){
        m = x % i;
        n = y % i;
        if (m == 0 && n == 0){
            sum *= i;
            x /= i;
            y /= i;
            i = 2;
        }
        else
            i++;
    }    
    return sum;
}

//最小公倍数函数
int LCM(int p, int q){
    int lc;
    lc = p * q / sum;
    return lc;
}

int main(){
    int a, b, hcf, lcm;
    
    scanf("%d %d", &a, &b);                       //输入两个整数
    
    hcf = HCF(a, b);                              //调用最大公约数函数
    lcm = LCM(a, b);                              //调用最小公倍数函数
    printf("HCF is %d  LCM is %d\n", hcf, lcm);   //输出最大公约数和最小公倍数
    
    system("pause");
    return 0;
}

方法2：

#include <>
#include <>

//最大公约数函数（利用欧几里得算法）
int HCF(int x, int y){
	for (int z = x % y; z != 0; x = y, y = z, z = x % y);
	return y;
}

//最小公倍数函数
int LCM(int x, int y)
{
	return (x * y) / HCF(x, y);
}

int main(){
	int a, b;
	
	printf("Please enter 2 numbers: ");               //输入两个整数
	scanf("%d %d", &a, &b);
	printf("HCF = %d, LCM = %d\n", HCF(a, b), LCM(a, b)); //输出最大公约数和最小公倍数
	
	system("pause");
	return 0;
}

解答第二条评论，处理数组n个元素的最大公约数

#include <>
#include <>

int HCF(int x, int y)
{
	for (int z = x % y; z != 0; x = y, y = z, z = x % y);
	return y;
}

int main(){
	int n[4], temp;
	
	for(int i = 0; i < 4; i++){
		printf("Please enter No.%d number: ", i + 1);
		scanf("%d", &n[i]);
	}
	for(int i = 0, temp = n[0]; i < 4; i++)
		temp = HCF(temp, n[i]);
	printf("HCF = %d\n", temp);
	
	system("pause");
	return 0;
}