最大公约数和最小公倍数（C语言）
基本要求： 求N个数的最大公约数和最小公倍数。用C或C++或java或python语言实现程序解决问题。
- 题目分析
辗转相除法（又名欧几里德法）C语言中用于计算两个正整数a,b的最大公约数和最小公倍数，实质它依赖于下面的定理：
a b=0
gcd(a,b) =
gcd(b,a mod b) b!=0
求N个数的最大公约数和最小公倍数思想和其一样，通过调用函数实现。
2.算法构造
最大公约数和最小公倍数的关系：假设有a,b两个数，p,q分别是它们的最大公约数和最小公倍数，则有:q=(a*b)/p。要求n个数的最大公约数，只需先求出两个数的最大公约数，然后再将这两个数求出的结果和下一个数求最大公约数就可以了，如此往复，即可求出这n个数的最大公约数。
3.算法实现（程序源代码）
#include <stdio.h>
#include<stdlib.h>
/*辗转相除法*/
int divisor1(int a,int b) /*自定义函数求两数的最大公约数*/
{
int temp; /*定义整型变量*/
if(a<b) /*通过比较求出两个数中的最大值和最小值*/
{
temp=a; /*设置中间变量进行两数交换*/
a=b;
b=temp;
}
while(b!=0) /*通过循环求两数的余数，直到余数为0*/
{
temp=a%b;
a=b; /*变量数值交换*/
b=temp;
}
return a; /*返回最大公约数到调用函数处*/
}
int divisor2(int t[],int n) /*求n个数的最大公约数*/
{
int i;
int c=t[0];
for(i=1;i<n;i++)
{
c=divisor1(c,t[i]);
}
return c;
}
int multiple1(int a,int b) /*自定义函数求两数的最小公倍数*/
{
int divisor1(int a,int b); /*自定义函数返回值类型*/
int temp;
temp=divisor1(a,b); /*再次调用自定义函数，求出最大公约数*/
return (a*b/temp); /*返回最小公倍数到主调函数处进行输出*/
}
int multiple2(int t[],int n) /*求n个数的最小公倍数*/
{
int i;
int d=1;
for(i=0;i<n;i++)
{
d=multiple1(d,t[i]);
}
return d;
}
int main()
{ int N,n,m,i,a[100],b[4],sum=0,x=0;
printf("您要求几个数字的最大公约数:\n");
scanf("%d",&n);
printf("请输入%d个数字:\n",n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
if(a[i]<0)
{
printf("请重新输入第%d个数:\n",i+1);
scanf("%d",&a[i]);
}
}
printf("这%d个数的最大公约数为%d\n",n,divisor2(a,n));
printf("这%d个数的最小公倍数为%d\n",n,multiple2(a,n));
//提高要求
printf("您要输入几组数据:\n");
scanf("%d",&N);
printf("请输入数据:\n");
for(;N>0;N--)
{
for(m=0;m<4;m++)
{
scanf("%d",&b[m]);
}
if(b[0]%b[1]||b[3]%b[2]) //判断是否满足题目条件
printf("输入不符合条件，请重新输入：\n");
for(m=0;m<4;m++)
{
scanf("%d",&b[m]);
}
for( x;x<=b[3];x++) //循环计算有多少个满足条件的数
{
if(divisor1(x,b[0])==b[1]&&multiple1(x,b[2])==b[3]) //调用计算最大公约数和最小公倍数的函数
sum++;
}
printf("一共有%d个数满足条件\n",sum);
}
}4.调试、测试及运行结果
- 调试结果
输入3,9,12
在multiple2（）函数出调试，截图如下所示
- 测试结果
1.测试最大公约数
#include <stdio.h>
#include<stdlib.h>
/*辗转相除法*/
int divisor1(int a,int b) /*自定义函数求两数的最大公约数*/
{
int temp; /*定义整型变量*/
if(a<b) /*通过比较求出两个数中的最大值和最小值*/
{
temp=a; /*设置中间变量进行两数交换*/
a=b;
b=temp;
}
while(b!=0) /*通过循环求两数的余数，直到余数为0*/
{
temp=a%b;
a=b; /*变量数值交换*/
b=temp;
}
return a; /*返回最大公约数到调用函数处*/
}
int divisor2(int t[],int n) /*求n个数的最大公约数*/
{
int i;
int c=t[0];
for(i=1;i<n;i++)
{
c=divisor1(c,t[i]);
}
return c;
}
int main()
{
int n,i,a[100];
printf("您要求几个数字的最大公约数:\n");
scanf("%d",&n);
printf("请输入%d个数字:\n",n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
if(a[i]<0)
{
printf("请重新输入第%d个数:\n",i+1);
scanf("%d",&a[i]);
}
}
printf("这%d个数的最大公约数为%d\n",n,divisor2(a,n));
return 0;
} 截图如下所示：
- 测试最小公倍数
#include <stdio.h>
#include<stdlib.h>
/*辗转相除法*/
int divisor1(int a,int b) /*自定义函数求两数的最大公约数*/
{
int temp; /*定义整型变量*/
if(a<b) /*通过比较求出两个数中的最大值和最小值*/
{
temp=a; /*设置中间变量进行两数交换*/
a=b;
b=temp;
}
while(b!=0) /*通过循环求两数的余数，直到余数为0*/
{
temp=a%b;
a=b; /*变量数值交换*/
b=temp;
}
return a; /*返回最大公约数到调用函数处*/
}
int multiple1(int a,int b) /*自定义函数求两数的最小公倍数*/
{
int divisor1(int a,int b); /*自定义函数返回值类型*/
int temp;
temp=divisor1(a,b); /*再次调用自定义函数，求出最大公约数*/
return (a*b/temp); /*返回最小公倍数到主调函数处进行输出*/
}
int multiple2(int t[],int n) /*求n个数的最小公倍数*/
{
int i;
int d=1;
for(i=0;i<n;i++)
{
d=multiple1(d,t[i]);
}
return d;
}
int main()
{
int n,i,a[100];
printf("您要求几个数字的最大公约数和最小公倍数:\n");
scanf("%d",&n);
printf("请输入%d个数字:\n",n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
if(a[i]<0)
{
printf("请重新输入第%d个数:\n",i+1);
scanf("%d",&a[i]);
}
}
printf("这%d个数的最小公倍数为%d\n",n,multiple2(a,n));
return 0;
}截图如下所示：
- 运行结果
1.输入两个互质的自然数，截图如下所示
2.输入两个自然数
3.输入三个有公约数的自然数
4.输入三个互质的自然数
5.经验归纳
此次实验在上次求两个最大公约数的基础上进行了扩展，相对来说比较简单，通过调用函数来实现求N个最大公约数和最小公倍数的功能，在上次实验的基础上做此次实验，就感觉比较简单，所以还是要多多练习，不断实践！Hankson问题基本要求实现了，但是还是没有代码可读性不高，还需继续完善修改。具体完善后再修改~~~Fighting