輾轉相除法求最大公約數c語言
❶ c語言求兩個數的最大公約數
思路：求兩個數的最大公約數使用輾轉相除法。
輾轉相除法，
又名歐幾里德演算法（Euclidean
algorithm）乃求兩個正整數之最大公因子的演算法。原理：兩個整數的最大公約數等於其中較小的數和兩數的差的最大公約數。
參考代碼：
#include <stdio.h>
int main()
{
int x,y,z;
scanf("%d%d",&x,&y);
while(x!=0)
{
z=x%y;
x=y;
y=z;
}
printf("%d\n",z);
return 0;
}
/*
運行結果：
6 27
3
*/
❷ 什麼是c語言裡面的輾轉相除法
用輾轉相除法（即歐幾里得演算法）求兩個正整數的最大公約數。
解析：
設兩個數m,n，假設m>=n，用m除以n，求得余數q。若q為0，則m為最大公約數；若q不等於0，則進行如下迭代：
m=n,n=q,即原除數變為新的被除數，原余數變為新的除數重復演算法，直到余數為0為止。余數為0時的除數n，即為原始m、n的最大公約數。
迭代初值：m，n的原始值；
迭代過程：q=m%n;
m=n;
n=q;
迭代條件：q!=0
例如：m=8;n=6
q=m%n(8%6==2)
m=n(m==6)
n=q(n==2)
因為：(q==2)!=0，重復演算法：
q=m%n(6%2==0)
m=n(m==2)余數為0時的除數n為最大公約數，n值賦給了m，所以輸出m的值
n=q(n==0)
因為：q==0 所以最大公約數為m的值
源程序：
#include<stdio.h>
void main()
{
int m,n,q,a,b;
printf("Enter two integers:");
scanf("%d%d",&a,&b);
m=a;
n=b;
if(n>m)
{
int z;
z=m;m=n;n=z;//執行演算法前保證m的值比n的值大
}
do
{
q=m%n;
m=n;
n=q;
}while(q!=0);
printf("The greatest common divisor of");
printf("%d,%d is %d\n",a,b,m);
}
希望對你有所幫助!
❸ 如何用C語言求兩個數的最大公約數的三種演算法
1、相減法
#include<stdio.h>
int main()
{
int a,b;
int c=0;//計數器
while(1)//循環判斷的作用
{
printf("輸入兩個數字求最大公約數:");
scanf("%d%d",&a,&b);
while(a!=b)
{
if(a>b)
a=a-b;
else
b=b-a;
c++;
}
printf("最大公約數是:%d ",a);
printf("%d ",c);
}
return 0;
}
運行效果：
2、輾轉相除法：
#include<stdio.h>
int a,b,temp;
int Division(){
printf("請輸入兩個數(a,b)： ");
scanf("%d,%d",&a,&b);
if(a<b){
temp=a;
a=b;
b=temp;
}
while(a%b!=0){
temp=a%b;
a=b;
b=temp;
}
printf("最大公約數為：%d ",b);
return 0;
}
3、窮舉法
#include<stdio.h>
int main()
{
int a,b,c;
int d=0;//計數器
while(1)
{
printf("輸入兩個數字求最大公約數:");
scanf("%d%d",&a,&b);
c=(a>b)?b:a;//三目運算符
while(a%c!=0||b%c!=0)
{
c--;
d++;
}
printf("最大公約數是:%d ",c);
printf("%d ",d);
}
return 0;
}
❹ c語言編程,利用輾轉相除法求公約數
輾轉相除法， 又名歐幾里德演算法（Euclidean algorithm）乃求兩個正整數之最大公因子的演算法。
其原理如下：
設兩數為a、b(b<a)，用gcd(a,b)表示a，b的最大公約數，r=a (mod b) 為a除以b以後的余數，k為a除以b的商，即a÷b=k.......r。輾轉相除法即是要證明gcd(a,b)=gcd(b,r）。
第一步：令c=gcd(a,b），則設a=mc，b=nc
第二步：根據前提可知r =a-kb=mc-knc=(m-kn)c
第三步：根據第二步結果可知c也是r的因數
第四步：可以斷定m-kn與n互質【否則，可設m-kn=xd，n=yd (d>1)，則m=kn+xd=kyd+xd=(ky+x)d，則a=mc=(ky+x)dc，b=nc=ycd，故a與b最大公約數成為cd，而非c，與前面結論矛盾】
從而可知gcd(b,r)=c，繼而gcd(a,b)=gcd(b,r)。
證畢。
以上步驟的操作是建立在剛開始時r!=0的基礎之上的。即m與n亦互質。
按照其規則，C語言實現如下：
intGCD(inta,intb)
{returnb==0？a:GCD(b,a%b)；}
❺ c語言輾轉相除法求最大公約數和最小公倍數
c語言輾轉相除法求最大公約數和最小公倍數的方法如下：
一、演算法思想
利用格式輸入語句將輸入的兩個數分別賦給a和b，然後判斷a和b的關系，如果a小於b，則利用中間變數t將其互換。再利用輾轉相除法求出最大公約數，進而求出最小公倍數。最後用格式輸出語句將其輸出。
3、輾轉相除法： 是求最大公約數的一種方法。即用較小數除較大數，再用出現的余數（第一餘數）去除除數，再用出現的余數（第二餘數）去除第一餘數，如此反復，直到最後余數是0為止。如果是求兩個數的最大公約數，那麼最後的除數就是這兩個數的最大公約數。
❻ 編程一個C語言程序,輸入兩個數,採用輾轉相除法來計算最大公約數
可以參考下面的代碼：
#include <stdio.h>
int main()
{
int m, n, r;
scanf ("%d%d", &m, &n);
if (m>n){r=m, m=n, n=r;}
r=n%m;
while (r!=0){
n = m;
m = r;
r = n%m;
}
printf ("%d ", m);
return 0;
}
(6)輾轉相除法求最大公約數c語言擴展閱讀：
函數 scanf() 是從標准輸入流stdin(標准輸入設備，一般指向鍵盤)中讀內容的通用子程序，可以說明的格式讀入多個字元，並保存在對應地址的變數中。
函數的第一個參數是格式字元串，它指定了輸入的格式，並按照格式說明符解析輸入對應位置的信息並存儲於可變參數列表中對應的指針所指位置。每一個指針要求非空，並且與字元串中的格式符一一順次對應。