c語言輾轉相除法求最大公約數
① c語言輾轉相除法求最大公約數
可用遞歸來求。
推薦以下代碼：
#include<stdio.h>
intgcd(inta,intb)//求最大公約數函數
{
if(a%b==0)returnb;
elsereturngcd(b,a%b);//輾轉相除法
}
voidmain()
{
inta,b;
scanf("%d%d",&a,&b);
printf("%d ",gcd(a,b));
}
② c語言中，用輾轉相除法計算兩個數的最大公約數的具體方法是怎樣的
#include <stdio.h>
int gcd(int a, int b) {
int r;
do {
r = a % b;
a = b;
b = r;
} while (r);
return a;
}
int main(void) {
int a, b;
printf("Input two integers: \n");
scanf("%d%d", &a, &b);
printf("The greatest common divisor is: %d\n", gcd(a, b));
return 0;
}
原理：
輾轉相除法是利用以下性質來確定兩個正整數 a 和 b 的最大公因子的：
1. 若 r 是 a ÷ b 的余數，則
gcd(a,b) = gcd(b,r)
2. a 和其倍數之最大公因子為 a。
另一種寫法是：
1. a ÷ b，令r為所得余數（0≤r<b）
若 r = 0，演算法結束；b 即為答案。
2. 互換：置 a←b，b←r，並返回第一步
③ 編程一個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;
}
(3)c語言輾轉相除法求最大公約數擴展閱讀：
函數 scanf() 是從標准輸入流stdin(標准輸入設備，一般指向鍵盤)中讀內容的通用子程序，可以說明的格式讀入多個字元，並保存在對應地址的變數中。
函數的第一個參數是格式字元串，它指定了輸入的格式，並按照格式說明符解析輸入對應位置的信息並存儲於可變參數列表中對應的指針所指位置。每一個指針要求非空，並且與字元串中的格式符一一順次對應。
④ c語言輾轉相除法求多個數的最大公約數的思路,求簡化
#include<stdio.h>
intmain(){
inta,b,t,mod;
intnum=1;
printf("請輸入若干數，0表示結束 ");
printf("請輸入第%d個數：",num++);
scanf("%d",&b);
a=b;
while(a!=0)
{
printf("請輸入第%d個數：",num++);
scanf("%d",&a);
if(a==0)break;
if(a<b){
t=a;a=b;b=t;
}
mod=a%b;
while(mod)
{
a=b;
b=mod;
mod=a%b;
}
}
printf(" 共%d個數，最大公約數：%d ",num-2,b);
return0;
}
⑤ C語言程序:用「輾轉相除法」求兩個正整數的最大公約數(程序填空)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
int main()
{
int a, b,r;
scanf("%d %d", &a, &b);
while (b != 0)//當其中一個數為0，另一個數就是兩數的最大公約數
{
r = a%b;
a = b;
b = r;
}
printf("最大公約數%d ", a);
system("pause");
}
例子：
105252
252％105＝42；
105％42＝21；
42％21＝0；
即21為105與252的最大公約數
(5)c語言輾轉相除法求最大公約數擴展閱讀：
while語句若一直滿足條件，則會不斷的重復下去。但有時，需要停止循環，則可以用下面的三種方式：
一、在while語句中設定條件語句，條件不滿足，則循環自動停止。
如：只輸出3的倍數的循環；可以設置范圍為：0到20。
二、在循環結構中加入流程式控制制語句，可以使用戶退出循環。
1、break流程式控制制：強制中斷該運行區內的語句，跳出該運行區，繼續運行區域外的語句。
2、continue流程式控制制：也是中斷循環內的運行操作，並且從頭開始運行。
⑥ 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語言代碼
輾轉相除法是在在維基網路中的意思是：
在數學中，輾轉相除法，又稱歐幾里得演算法（英語：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語言程序
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; /*返回最大公約數到調用函數處*/
}
⑨ c語言如何求最大公約數和最小公倍數
#include <stdio.h>
int main()
{
int a,b,c,m,t;
printf("請輸入兩個數: ");
scanf("%d%d",&a,&b);
if(a<b)
{
t=a;
a=b;
b=t;
}
m=a*b;
c=a%b;
while(c!=0)
{
a=b;
b=c;
c=a%b;
}
printf("最大公約數是: %d ",b);
printf("最小公倍數是: %d ",m/b);
}
(9)c語言輾轉相除法求最大公約數擴展閱讀
演算法思想
利用格式輸入語句將輸入的兩個數分別賦給 a 和 b，然後判斷 a 和 b 的關系，如果 a 小於 b，則利用中間變數 t 將其互換。
再利用輾轉相除法求出最大公約數，進而求出最小公倍數。最後用格式輸出語句將其輸出。
#include<stdio.h>是在程序編譯之前要處理的內容，稱為編譯預處理命令。編譯預處理命令還有很多，它們都以「#」開頭，並且不用分號結尾，所以是c語言的程序語句。