最大公約數和最小公倍數- IT閱讀

二、算法思想及代碼. 求最小公倍數算法：最小公倍數=兩整數的乘積÷最大公約數. 求最大公約數算法：. （1）輾轉 ... 最大公約數和最小公倍數 首頁 最新 HTML CSS JavaScript jQuery Python3 Python2 Java C C++ Go SQL 首頁 最新 Search 最大公約數和最小公倍數 2017-05-06254 描述出現mage最大公約數imagescodegerreturnges一、問題描述 從鍵盤輸入兩個正整數a和b，求其最大公約數和最小公倍數。

二、算法思想及代碼 求最小公倍數算法：最小公倍數=兩整數的乘積÷最大公約數 求最大公約數算法： （1）輾轉相除法 用較大的數除以較小的數，再用除數除以出現的余數（第一余數），接著，再用第一余數除以出現的第二余數，如此反復，直到余數為0為止，最後的除數就是這兩個數的最大公約數。

有兩整數a和b： 　　①a%b得余數c 　　②若c=0，則b即為兩數的最大公約數 　　③若c≠0，則a=b，b=c，再回去執行① 例如求27和15的最大公約數過程為：27÷15余12，15÷12余3，12÷3余0，因此，3即為最大公約數。

#include intmain(){ intm,n,r,s; while(true){ printf("input2integers(mn):"); scanf("%d%d",&m,&n); if(m==0||n==0) break; if(mb，則a=a-b 　　②若a12)，15－12＝3(12>3)，12－3＝9(9>3)，9－3＝6(6>3)，6－3＝3(3==3)，因此，3即為最大公約數。

#include intmain(){ intm,n,s; while(true){ printf("input2integers(mn):"); scanf("%d%d",&m,&n); if(m==0||n==0) break; s=m*n;//保留乘積用於求最小公倍數 while(m!=n){ if(m>n) m=m-n; else n=n-m; } printf("最大公約數：%d\n",n);//最大公約數 printf("最小公倍數：%d\n\n",s/n);//最小公倍數 } return0; } （3）窮舉法 有兩整數a和b： 　　①i=1 　　②若a，b能同時被i整除，則t＝i 　　③i++ 　　④若i<=a(或b)，則再回去執行② 　　⑤若i>a(或b)，則t即為最大公約數，結束 改進： 　　①i=a(或b) 　　②若a，b能同時被i整除，則i即為最大公約數，結束 　　③i--，再回去執行② #include #include #defineN100 intgcd(intm,intn){ inti,k; for(i=2;i<=n;i++){ if(m%i==0&&n%i==0){ k=i;//保存當前的約數 continue; } } if(k<=n&&k>1) returnk; else return1; } intlcm(intm,intn){ intt=gcd(m,n); returnm*n/t; } intmain(){ intm,n,t; while(true){ printf("input2integers(mn):"); scanf("%d%d",&m,&n); if(m==0&&n==0) break; if(m intgcd(intm,intn){ inti,k; for(i=m;i>=2;i--){ if(m%i==0&&n%i==0){ returni; } } return1; } intlcm(intm,intn){ intt=gcd(m,n); returnm*n/t; } intmain(){ intm,n,s,t; while(true){ printf("input2integers(mn):"); scanf("%d%d",&m,&n); if(m==0&&n==0) break; printf("最大公約數：%d\n",gcd(m,n));//求最大公約數 printf("最小公倍數：%d\n\n",lcm(m,n));//求最小公倍數 } return0; } //求最小公倍數的程序：最大公約數可以用兩個數的求法遞歸實現，也可以先求出所有公約數，再比較得出最大值。

#include usingnamespacestd; intmain() { inta[5]={46,252,198,2366,3188}; inti,n; for(n=1;;n++) { i=n*3188; if((i%46==0)&&(i%252==0)&&(i%198==0)&&(i%2366==0)) { cout< /*最大公約數*/ intgcd(inta,intb) { intt; if(a