c語言歐幾里得演算法
① 什麼是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語言編程,利用輾轉相除法求公約數
輾轉相除法， 又名歐幾里德演算法（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語言:
int gcd(int a,int b)
{return b?gcd(b,a%b):a;
}
這是一個遞歸函數，直接調用就可以求得。
④ c語言求最大公約數輾轉相除法
int main(void)
{
printf("這是兩個整數求最大公約數的算式，請輸入兩個不相等的正整數，並按回車鍵確認：\n"); //操作提示
intm,n,r,i; //定義四個整形變數
scanf("%d %d",&m,&n); //輸入m和n的值
if(m<n) {i=m;m=n;n=i;} //如果m<n，借用變數i進行m和n的數值互換
while(m%n!=0) //m取模n 賦值給r
{r=a%b;m=n;n=r;} //余數不等於0，則n的值給m，r的值給n，再次進入循環
printf("它們的最大公約數是%d\n",n);
system("PAUSE");
return 0;
}
⑤ C語言用歐幾里得演算法定義的求最大公約數的函數沒看懂，哪位大神能解釋一下具體到每一步驟。
if(x<y) {t=x;x=y;y=t;} //交換，使得x是兩數中最大值，y是最小值
while(y!=0) {t=x%y;x=y;y=t;} //演算法核心，首先用x模y，取得余數，然後每次用除數模余數，直到整除為止
⑥ 用歐幾里得演算法（輾轉相除法）求最大公約數,C語言編程
你的程序是正確的，
瑕疵在於
scanf("%d,%d",&m,&n);
scanf函數，雙引號內光寫格式就好了，不用寫逗號什麼的，多寫什麼程序運行的時候就要輸入什麼。如你所寫，運行時就應輸入：12，24 若你在12與24之間按的是空格或其他有可能影響到第二個變數取不到值。
所以建議改為
scanf("%d%d",&m,&n); 程序運行要求輸入時兩個數之間按空格回車隨你。
⑦ C語言輾轉相除法問題
#include <stdio.h>
int fun(int a,int b) /* 2個數的公約數 */
{
int t;
while(b)
{
t = a%b;
a = b;
b = t;
}
return a;
}
int main()
{
int a[100];
int n;
int i;
int res;
scanf("%d",&n); /* 先輸入數的總數n */
if(n < 2)
{
printf("n不能小於2
");
return 0;
}
for(i=0;i<n;i++) /* 輸入n個數 */
scanf("%d",&a[i]);
res = fun(a[0],a[1]);
for(i=2;i<n;i++)
res = fun(res,a[i]);
printf("%d
",res);
return 0;
}
⑧ 歐幾里得演算法（輾轉相除法）
就是把上一輪有餘數的除法計算中，
除數變為下一輪計算的被除數，
余數變為下一輪計算的除數，
一直這樣計算下去，
直到最後一次計算余數為零，
在最後一輪計算中的被除數，即為所求的最大公約數。
舉例：
105和85的最大公約數
第一輪計算
105÷85=1...20
第二輪計算
85÷20=4...5
第三輪計算
20÷5=4
第三輪沒有餘數，
因此
105和85的最大公約數就是第三輪計算的被除數
5.
至於C語言編程，下邊是我自己寫的G函數(思想就是輾轉相除法求最大公約數)
int
G(int
x,int
y)
{
int
t;
while(y!=0)
{
t=x%y
;
x=y;
y=t;
}
return
x;
}
⑨ 輾轉相除法求最大公約數c語言代碼
輾轉相除法是在在維基網路中的意思是：
在數學中，輾轉相除法，又稱歐幾里得演算法（英語：Euclidean algorithm），是求最大公約數的演算法。輾轉相除法首次出現於歐幾里得的《幾何原本》（第VII卷，命題i和ii）中，而在中國則可以追溯至東漢出現的《九章算術》。
兩個整數的最大公約數是能夠同時整除它們的最大的正整數。輾轉相除法基於如下原理：兩個整數的最大公約數等於其中較小的數和兩數的差的最大公約數。例如，252和105的最大公約數是21（ {\displaystyle 252=21\times 12;105=21\times 5} {\displaystyle 252=21\times 12;105=21\times 5}）；因為 252 − 105 = 21 × (12 − 5) = 147 ，所以147和105的最大公約數也是21。在這個過程中，較大的數縮小了，所以繼續進行同樣的計算可以不斷縮小這兩個數直至其中一個變成零。這時，所剩下的還沒有變成零的數就是兩數的最大公約數。由輾轉相除法也可以推出，兩數的最大公約數可以用兩數的整數倍相加來表示，如 21 = 5 × 105 + (−2) × 252 。這個重要的結論叫做裴蜀定理。
在現代密碼學方面，它是RSA演算法（一種在電子商務中廣泛使用的公鑰加密演算法）的重要部分
簡單的來說輾轉相除法的原理就是：
先比較兩個數使第一個數為最大數a，第二個數為最小數b
使最大數%最小數得到余數a%b=temp
後將余數賦值給最小數a=temp再去除最大數b即b%a
一直往復直到余數不為0