最大公約數輾轉相除法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語言程序:用「輾轉相除法」求兩個正整數的最大公約數(程序填空)
#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的最大公約數
(2)最大公約數輾轉相除法c語言擴展閱讀：
while語句若一直滿足條件，則會不斷的重復下去。但有時，需要停止循環，則可以用下面的三種方式：
一、在while語句中設定條件語句，條件不滿足，則循環自動停止。
如：只輸出3的倍數的循環；可以設置范圍為：0到20。
二、在循環結構中加入流程式控制制語句，可以使用戶退出循環。
1、break流程式控制制：強制中斷該運行區內的語句，跳出該運行區，繼續運行區域外的語句。
2、continue流程式控制制：也是中斷循環內的運行操作，並且從頭開始運行。
『叄』 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>
#include<stdlib.h>
intmain()
{
inta,b,r;
scanf("%d%d",&a,&b);
while(b!=0)//當其中一個數為0，另一個數就是兩數的最大公約數
{
r=a%b;
a=b;
b=r;
}
printf("GreatestCommonDivisor:%d ",a);
system("pause");
}
運行結果：
『伍』 編程一個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;
}
(5)最大公約數輾轉相除法c語言擴展閱讀：
函數 scanf() 是從標准輸入流stdin(標准輸入設備，一般指向鍵盤)中讀內容的通用子程序，可以說明的格式讀入多個字元，並保存在對應地址的變數中。
函數的第一個參數是格式字元串，它指定了輸入的格式，並按照格式說明符解析輸入對應位置的信息並存儲於可變參數列表中對應的指針所指位置。每一個指針要求非空，並且與字元串中的格式符一一順次對應。
『陸』 C語言求最大公約數
這個叫做輾轉相除法，是中國古代標準的求最大公約數的方法。兩個數正整數a〉b，如果a%b(a除b的余數)=0，b就是最大公約數;否則比較b與a÷b的余數c=a%b，兩者相除，余數為0,c是最大公約數;否則繼續比較c與b%c(余數)，……，反復交換進行，直到余數為0
『柒』 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語言代碼
輾轉相除法是在在維基網路中的意思是：
在數學中，輾轉相除法，又稱歐幾里得演算法（英語：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語言 公約數輾轉相除法
如果兩個數有最大公約數A，那麼這兩個數，以及這兩個數的差，還有大數除以小數的余數，必然都是A的倍數。
所以當最後兩個數剛好能整除時，較小的數就是最大公約數。
建議你單步調試
深刻理解。。
下面是更加具體的：
對於兩個數,我們要求是正整數,我們一般用輾轉相除法兩個數的最大公約數,下面我來仔細講講輾轉相除法兩個數的最大公約數的原理.
我們假設這兩個數分別是X,Y,他們最大的公約數為M,則有X=a*M,Y=b*M(a,b是互質的數),很明顯,我們的目的就是要把M的系數降到一,為此我們進行X%Y運算,實際上X%Y=(a%b)*M,由於a%b小於b,所以M的系數將會減小,接著我們進行Y%((a%b)*M)=(b%(a%b))*M,同理,則有b%(a%b)<(a%b),可見隨著這樣取余的操作M的系數會越來越小,前面已經說過,我們的目標是使M的系數降到一,而一是任何整數的約數,換句話說任何整數除一取余後為0,所以當取余之後的數為0,也就意味著M之前的系數為1,此時的被除數就是最大公約數,
舉個例子
24
與
15
24=8*3
15=5*3
24%15=(8%5)*3=3*3=9;
15%9=(5%3)*3=2*3=6
9%6=(3%2)*3=3
6%3=(2%1)*3=0
-------------------------------被除數3就是24與5的最大公約數
兩個正整數的最大公約數求出來之後他們的最小公倍數也就知道了,最小公倍數=兩個數相乘除以他們的最大公約數,
原理很簡單,不加詳述.
在
C++中,求最大公約數的代碼如下
int
gys(int
a,int
b)
//a必須要大於b
{
int
r=a%b;
while(r!=0)
{
a=b;
b=r;
r=a%b;
}
return
b;
}
求最小公倍數的代碼很簡單,如下
int
gbs(int
a,int
b)//a必須要大於b
{
return
a*b/gys(a,b);
}
好了,有錯誤之處還請指正
『拾』 c語言四種方法求最大公約數
c語言四種方法求最大公約數的方法依次是。第1種窮舉法。第2種輾轉相減法。第3種輾轉相除法（包括遞歸的和非遞歸的）。