歐幾里德演算法c語言
① 鍒ゆ柇涓や釜鏁癮,b鏄鍚︿負浜掕川鏁扮殑紼嬪簭錛岀敤C璇璦緙栧啓錛
涓や釜鏁頒簰璐錛屽氨鏄璇翠袱涓鏁扮殑娌℃湁鍏鍏卞洜瀛愶紝鍗蟲渶澶у叕綰︽暟鏄1
紼嬪簭濡備笅錛
#include <stdio.h>
int GCD(int x,int y)//鏈澶у叕綰︽暟鍑芥暟錛屾у嚑閲屽痙綆楁硶
{
int a,b,c;
if(x>y)
{a=x,b=y;}
else
{a=y,b=x;}
while ((a%b)!=0)
{
c=a%b;
a=b;
b=c;
}
return b;
}
int main()
{
int m,n;
printf("please input two positive numbers:");
scanf("%d%d",&m,&n);
if(GCD(m,n)>1)
printf("涓や釜鏁頒笉鏄浜掕川鐨勩\n");
else
printf("涓や釜鏁版槸浜掕川鐨勩\n");
}
杈撳叆紺轟緥錛100 3
杈撳嚭錛氫袱涓鏁版槸浜掕川鐨勩
紼嬪簭鍦―EV C++涓嬭皟璇曢氳繃錛屾渶澶у叕綰︽暟璁＄畻浣跨敤鐨勬槸嬈у嚑閲屽痙綆楁硶錛堟暟璁哄熀紜鐭ヨ瘑錛夛紝鐪嬭繃灝辨槑鐧戒簡銆
歐幾里德演算法求最大公因數c語言:
int gcd(int a,int b)
{return b?gcd(b,a%b):a;
}
這是一個遞歸函數，直接調用就可以求得。
③ 輾轉相除法求最大公約數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
④ 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)；}
⑤ 牛頓迭代法的示例
最經典的迭代演算法是歐幾里德演算法，用於計算兩個整數a,b的最大公約數。其計算原理依賴於下面的定理：
定理：gcd(a,b) = gcd(b,a mod b)
證明：a可以表示成a = kb + r，則r = a mod b。假設d是a,b的一個公約數，則有 a%d==0,b%d==0，而r = a - kb，因此r%d==0 ，因此d是(b,a mod b)的公約數
同理，假設d 是(b,a mod b)的公約數，則 b%d==0,r%d==0 ，但是a = kb +r ，因此d也是(a,b)的公約數。
因此(a,b)和(b,a mod b)的公約數是一樣的，其最大公約數也必然相等，得證。
歐幾里德演算法就是根據這個原理來做的，歐幾里德演算法又叫輾轉相除法，它是一個反復迭代執行，直到余數等於0停止的步驟，這實際上是一個循環結構。其演算法用C語言描述為： intGcd_2(inta,intb)/*歐幾里德演算法求a,b的最大公約數*/{if(a<=0||b<=0)/*預防錯誤*/return0;inttemp;while(b>0)/*b總是表示較小的那個數，若不是則交換a，b的值*/{temp=a%b;/*迭代關系式*/a=b;b=temp;}returna;}從上面的程序我們可以看到a，b是迭代變數，迭代關系是temp = a % b；根據迭代關系我們可以由舊值推出新值，然後循環執a = b; b = temp；直到迭代過程結束（余數為0）。在這里a好比那個膽小鬼，總是從b手中接過位置，而b則是那個努力向前沖的先鋒。 還有一個很典型的例子是斐波那契（Fibonacci）數列。斐波那契數列為：0、1、1、2、3、5、8、13、21、…，即 fib⑴=0; fib⑵=1;fib(n)=fib(n-1)+fib(n-2) （當n>2時）。
在n>2時，fib(n)總可以由fib(n-1)和fib(n-2)得到，由舊值遞推出新值，這是一個典型的迭代關系，所以我們可以考慮迭代演算法。 intFib(intn)//斐波那契（Fibonacci）數列{if(n<1）/*預防錯誤*/return0;if(n==1||n==2)/*特殊值，無需迭代*/return1;intf1=1,f2=1,fn;/*迭代變數*/inti;for(i=3;i<=n;++i)/*用i的值來限制迭代的次數*/{fn=f1+f2;/*迭代關系式*/f1=f2;//f1和f2迭代前進，其中f2在f1的前面f2=fn;}returnfn;}
⑥ 用C語言編制的求模逆元的擴展歐幾里德演算法，只要能基本上實現這個功能就行
擴展歐幾里德演算法是用來在已知a, b求解一組x，y，使它們滿足貝祖等式： ax+by = gcd(a, b) =d（解一定存在，根據數論中的相關定理）。擴展歐幾里德常用在求解模線性方程及方程組中。
下面是一個使用C語言的實現：
intexGcd(inta,intb,int&x,int&y)
{
if(b==0)//當b==0時，得到解
{
x=1;y=0;
returna;
}
intr=exGcd(b,a%b,x,y);//遞歸調用自身，求解
intt=x;x=y;y=t-a/b*y;
returnr;
}