c语言求最大公约数

c语言求最大公约数

平台用户的互动中精选与c语言求最大公约数相关的:1、用C语言求最大公约数。 2、c语言求两个正整数的最大公约数 3、C语言构造求最大公约数算法 4、C语言求最大公约数 5、用C语言编写一个可以求输入的两个数的最大公约数和最小公倍数的程序。 6、编写一个c语言程序 求两个整数的最大公约数 7、c语言求最大公约数穷举法 8、C语言 用辗转相除法求最大公约数 编写C语言程序 9、C语言求最大公约数 10、c语言如何求最小公倍数和最大公约数
c语言求最大公约数
平台用户 2018-06-06 16:47:44

下面是精选平台用户互动时的最佳讨论

匿名
匿名


匿名:用C语言求最大公约数。

下面的解答已被2957人点赞

#include <stdio.h>
int main(int argc,char *argv[]){
    int a,b,r;
    printf("Input a & b(int a,b>0)...\n");
    if(scanf("%d%d",&a,&b)!=2 || a<1 || b<1){
        printf("Input reeor, exit...\n");
        return 0;
    }
    while(b)
        r=a%b,a=b,b=r;
    printf("The GCD is %d\n",a);
    return 0;
}

最后一次编辑时间 2017-03-29
那爱佷灬眞诚
那爱佷灬眞诚


那爱佷灬眞诚:c语言求两个正整数的最大公约数

int gy(int m, int n)
{int t;
t=m%n;
while(t)
{m=n;
n=t;
t=m%n;
}
return n;}
求个步骤的详细就是,不加main()什么的吗 这样直接写对吗初学者 ,谢谢
下面的解答已被4843人点赞

求最大公约数的方法有很多。最常用的有如下两种:

1 根据数学定义,可同时整除两个操作数的最大整数,就是最大公约数:

int gcd(int m, int n)//求n和m的最大公约数
{
    int min = m>n?n:m; //两个数的较小者。
    while(min > 0)
    {
        if(m%min == 0 && n%min == 0) break;//都能整除,则为最大公约数。
        min--;
    }
    return min; 
}

2 在算法上,有专门的快速求最大公约数的算法,称为辗转相除法:

以下是该算法的递归实现:

int gcd(int x , int y)
{
    if(!y)return x;
    return gcd(y , x%y);
}

最后一次编辑时间 2015-12-11
枭角色
枭角色


枭角色:C语言构造求最大公约数算法

求教算法解析,百度了一下不太懂,就用辗转相除法法吧,也可以给出多种算法,希望在给出代码的时候后面给出解释谢谢,初学者比较啰嗦
下面的解答已被4649人点赞
int cacu(int a,int b){
int temp;
while(a!=0){
temp=b%a;
b=a;
a=temp;
}
return b;
}
构造函数返回最大公约数
我们用b作为这一次的被除数,a作为这一次的除数,则此次的余数为b%a,temp储存。接下来要为下一次运算做准备,在下一次运算中这次的除数要作为被除数出现,这次的余数要作为除数出现,故将对应的值分别放到对应的位置上(这次出书a的值赋给下一次的被除数b,这次余数temp的值赋给下次的除数a)。关于结束条件,由于余数为0时的除数是我们要求的值,但是在判定时这个值已经被我们当成下一次还未进行的运算的被除数赋给了b,而那个值为0的余数也被我们赋给了下一次的除数a,故可将下一次运算的除数为0作为结束条件,将下一次运算的被除数作为结果返回

纯手打,希望有帮助,给个采纳吧亲~

追问

你的回答很好,循环原理懂了,不懂的是,你这个是不是不完整啊?那个cacu什么意思?最让我困惑的就是在求余时怎么确定大除于小的?和上面有关?输出在哪?return b;?

追答

我的答案只是个计算函数,不是主函数,返回的是最大公约数

因为上面只是要算法,没有要程序,所以就没写主函数。想验证的话用下面这个吧:
int main(){
int a,b;
scanf("%d %d",&a,&b);
while(a!=0&&b!=0){
printf("%d\n",cacu(a,b));
scanf("%d %d",&a,&b);
}
return 0;
}
PS:cacu是caculate简短写法(个人习惯)

事实上不用确定谁大谁小

如果b>a,即和传统辗转相除无区别;如果a>b,则在执行下次循环时a、b会交换其值(即b%a的值为b,赋给下一次的a,而a的值赋给下一次的b)


另外,楼楼是不是没学写函数啊,其实也可以写成:

#include<stdio.h>
int main(){
    int a,b,temp;
    scanf("%d %d",&a,&b);
    while(a!=0){
        temp=b%a;
        b=a;
        a=temp;
    }
    printf("%d\n",b);
    return 0;
}

 return b;是在写分函数的时候确定返回值用的(估计楼楼过一段时间会了解到吧)

追问

cacu接上面的循环算法?

追答

c语言里可以自己写函数(比如上面的cacu函数),格式是
<返回值类型> <函数名>(<参数列表>){函数体}
已经定义的函数在其他函数中可以被调用,调用时需出现的结构为
<函数名>(<传入参数列表>);
再举个例子,scanf();和printf();就是两种相对特别一点的函数,main()函数也是一种函数,只是更为特殊

更多追问

最后一次编辑时间 2014-03-30
遗忘的痕迹
遗忘的痕迹


遗忘的痕迹:C语言求最大公约数

#include<stdio.h>
int main ()
{
int m,n,r,temp;
scanf("%d%d",&m,&n);
if (m<n)
{
temp=m,m=n,n=temp;
}
while(m)
{
r=m%n,m=n,n=r;
}
printf("%d",r);
return 0;
}

这个程序运行后会出错,怎么回事?
下面的解答已被2732人点赞
#include "stdio.h"
int main()
{
int d1,d2,r;
printf("输入两个正整数:");
scanf("%d %d",&d1,&d2);
do
{
r=d1%d2;
d1=d2;d2=r;
}while(d2!=0);
printf("最大公约数是:%d",d1);
}

//递归法
#include "stdio.h"
int fun(int d1,int d2)
{
if(d2!=0)
return fun(d2,d1%d2);
else
return d1;
}
int main()
{
int d1,d2;
printf("输入两个正整数:");
scanf("%d %d",&d1,&d2);
printf("最大公约数是:%d",fun(d1,d2));
}
最后一次编辑时间 2016-01-14
傻十三1314
傻十三1314


傻十三1314:用C语言编写一个可以求输入的两个数的最大公约数和最小公倍数的程序。


可以运行,不能得到答案

下面的解答已被3996人点赞
#include <stdio.h>
void main()
{
int m,n,k,min,max,i;
scanf("%d%d",&m,&n);
if(n<m)
{
k=n;
n=m;
m=k;
}
for(i=m;i>0;i++)
{
if((m%i==0)&(n%i==0))
{
max=i;
break;
}
}
min=m*n/max;
printf("%d和%d的最大公约数是%d\n",m,n,max);
printf("%d和%d的最小公倍数是%d\n",m,n,min);
}
这个是我的程序,其中利用了最小公倍数是两个数的乘积除以最大公倍数,希望能够帮到你。

追问

我还没学void 和for 可以用int型和while语句解决吗?

追答

#include <stdio.h>
int main()
{
int m,n,k,min,max,i;
scanf("%d%d",&m,&n);
if(n<m)
{
k=n;
n=m;
m=k;
}
i=m;
while(i>0)
{
if((m%i==0)&(n%i==0))
{
max=i;
break;
}
i--;
}
min=m*n/max;
printf("%d和%d的最大公约数是%d\n",m,n,max);
printf("%d和%d的最小公倍数是%d\n",m,n,min);
}
定义main函数的类型的时候,void和int是没有区别的,其实绝大多数时候定的是void,也就是空类型。for语句和while语句是一样的,这个是我修改后的程序,希望同样能帮到你。

追问

我看懂您求最大公约数的方法了,的确很新颖。如果要用辗转相除法应该怎么表示?

追答

#include<stdio.h>

int main()

{

int m,n,r,p,k;

scanf("%d%d",&m,&n);

if(n>m)

{

k=n;

n=m;

m=k;

}

p=m*n;

while(m!=0)

{

r=n%m;

n=m;

m=r;

}

printf("这是最大公约数:%d\n",n);

printf("这是最小公倍数:%d\n",p/n);

return 0;

}

这个是我给你修改后的程序,你的程序思路上是正确的,只是有两个细节错了。

  1. 两个数值比较的时候,if里面的语句应该是(n>m),,而不是(n<m);2

  2. while里面应该是(m!=0),而不是(m=0);

更多追问

最后一次编辑时间 2014-10-21
youyuzc
youyuzc


youyuzc:编写一个c语言程序 求两个整数的最大公约数

下面的解答已被1710人点赞
#include<stdio.h> 
int gongyue(int m,int n)
{
int r;
if(m==n) return m;
else
while((r=m%n)!=0)
{
m=n;
n=r;
}
return n;
}
void main()
{
int a,b,i;
printf("please input two number:\n");
scanf("%d%d",&a,&b);
i=gongyue(a,b);
printf("最大公约数是:%d\n",gongyue(a,b));
}
最后一次编辑时间 2010-12-28
八中陈晨
八中陈晨


八中陈晨:c语言求最大公约数穷举法

#include <stdio.h> int max(int x,int y) { int i; for(i=x;;i++) { if(x%i==0&&y%i==0) break; } return i; } int min(int x,int y) { int j; for(j=x;j>=1;j--) { if(j%x==0&&j%y==0) break; } return j; } int main(void) { in... #include <stdio.h>
int max(int x,int y)
{
int i;
for(i=x;;i++)
{
if(x%i==0&&y%i==0)
break;
}
return i;
}
int min(int x,int y)
{
int j;
for(j=x;j>=1;j--)
{
if(j%x==0&&j%y==0)
break;
}
return j;
}
int main(void)
{
int x,y,large,small;
scanf("%d%d",&x,&y);
large=max(x,y);
small=min(x,y);
printf("%d %d",large,small);
return 0;
}
下面的解答已被5031人点赞
#include "stdio.h"
void main()
{int a,m,n,i;
scanf("%d,%d",&m,&n);//
if(n>m)
{a=m;
m=n;
n=a;
}

for(i=n;i>=1;i--)
{ if(m%i==0&&n%i==0)
break;

}
printf("%d",i);
}
最后一次编辑时间 推荐于2016-11-03 20:23:31
一朵午荷lichen
一朵午荷lichen


一朵午荷lichen:C语言 用辗转相除法求最大公约数 编写C语言程序

下面的解答已被6952人点赞
int divisor (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; /*返回最大公约数到调用函数处*/
}
最后一次编辑时间 2014-10-24
千年伯爵__
千年伯爵__


千年伯爵__:C语言求最大公约数

#include"stdio.h" #define max(a,b) (((a)>(b)) ? (a):(b)) #define min(a,b) (((a)>(b)) ? (b):(a)) int main() { int i,j,k; scanf_s("%d%d",&i,&j); if(i=j){ printf("%d\n",i); } else{ while(i!=j) k=max(i,j)-min(i,j); ... #include"stdio.h"
#define max(a,b) (((a)>(b)) ? (a):(b))
#define min(a,b) (((a)>(b)) ? (b):(a))
int main()
{
int i,j,k;
scanf_s("%d%d",&i,&j);
if(i=j){
printf("%d\n",i);
}
else{
while(i!=j)
k=max(i,j)-min(i,j);
if(k>min(i,j)){
max(i,j)=k;
}
if(k<min(i,j)){
max(i,j)=min(i,j);
min(i,j)=k;
}
printf("%d\n",i);
}
}
这个程序运行后结果有问题,错在哪了?
下面的解答已被6280人点赞

#include"stdio.h"
#define max(a,b) (((a)>(b)) ? (a):(b))
#define min(a,b) (((a)>(b)) ? (b):(a))
int main()
{
    int i,j,k,mmax,mmin;
scanf("%d%d",&i,&j);
if(i==j){
   printf("%d\n",i);
}
else{
        mmax = max(i,j);
        mmin = min(i,j);
        while(mmax!=mmin){
             k=mmax-mmin;
             if(k>mmin){
                 mmax = k;
             }
             if(k<=mmin){
                 mmax=mmin;
                 mmin=k;
            }
            //printf("%d %d\n",mmax,mmin);
        }
        printf("%d\n",mmax);
}
return 0;
}

最后一次编辑时间 2016-12-20
闪神无敌75
闪神无敌75


闪神无敌75:c语言如何求最小公倍数和最大公约数

下面的解答已被6805人点赞

//求两个数的最大公约数和最小公倍数
void fun(int a,int b)
{
    int temp,r;
    int v;
     
    if(a<b)
    {temp=a; a=b; b=temp;}    //将大数放在a中,小数放在b
    v=a*b;
    r=a%b;
    while(r!=0)
    {
        a=b;
        b=r;
        r=a%b;
    }
    v/=b;
    printf("最大公约数为%d\n",b);
    printf("最小公倍数为%d\n",v);
}

这是求最小公倍数和最大公约数的函数,希望对你有所帮助。

最后一次编辑时间 推荐于2017-12-16 14:04:51