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
金蟾捕鱼单机下载