求最小公倍數算法：

最小公倍數=兩整數的乘積÷最大公約數

求最大公約數算法：

(1)輾轉相除法

有兩整數a和b：

①?a%b得余數c

②?若c=0，則b即為兩數的最大公約數

③ 若c≠0，則a=b，b=c，再回去執行①

例如求27和15的最大公約數過程為：

27÷15?余1215÷12余312÷3余0因此，3即為最大公約數

?

[cpp]?view plain?copy

1. #include<stdio.h>??
2. void?main()???/*??輾轉相除法求最大公約數?*/???
3. {???
4. ???int?m,?n,?a,?b,?t,?c;??
5. ???printf("Input?two?integer?numbers:\n");??
6. ???scanf("%d%d",?&a,?&b);??
7. ???m=a;???n=b;??
8. ???while(b!=0)??/*?余數不為0，繼續相除，直到余數為0?*/???
9. ???{?c=a%b;?a=b;??b=c;}??
10. ???printf("The?largest?common?divisor:%d\n",?a);??
11. ???printf("The?least?common?multiple:%d\n",?m*n/a);??
12. }??

?

⑵ 相減法

有兩整數a和b：

① 若a>b，則a=a-b

② 若a<b，則b=b-a

③ 若a=b，則a（或b）即為兩數的最大公約數

④ 若a≠b，則再回去執行①

例如求27和15的最大公約數過程為：

27－15＝12( 15>12 ) 15－12＝3( 12>3 )

12－3＝9( 9>3 ) 9－3＝6( 6>3 )

6－3＝3( 3==3 )

因此，3即為最大公約數

?

[cpp]?view plain?copy

1. #include<stdio.h>??
2. void?main?(?)??/*?相減法求最大公約數?*/??
3. {????
4. ???int?m,?n,?a,?b,?c;??
5. ?? ?printf("Input?two?integer?numbers:\n");??
6. ???scanf?("%d,%d",?&a,?&b); m=a;?n=b;???
7. ?????/*?a,?b不相等，大數減小數，直到相等為止。*/? ??
8. ???while?(?a!=b)???
9. ?????????if?(a>b)??a=a-b; ???????
10. ?????????else??b=b-a; ??
11. ???printf("The?largest?common?divisor:%d\n",?a);??
12. ???printf("The?least?common?multiple:%d\n",?m*n/a);??
13. }??

?

?

?

⑶窮舉法

有兩整數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--，再回去執行②

有兩整數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--，再回去執行②

?

[cpp]?view plain?copy

1. #include<stdio.h>??
2. void?main?()??/*?窮舉法求最大公約數?*/??
3. {????
4. ???int??m,?n,?a,?b,?i,?t; ??
5. ???printf("Input?two?integer?numbers:\n");??
6. ???scanf?("%d,%d",?&a,?&b); m=a;??n=b;???
7. ???for?(i=1;?i<=?a;?i++)????
8. ???????if?(?a%i?==?0?&&?b%i?==0?)????t=i;??
9. ???printf("The?largest?common?divisor:%d\n",?t);??
10. ???printf("The?least?common?multiple:%d\n",?m*n/t);??
11. }???
12. /*??改進后的?
13. ???for?(t=?a;?t>0;?t--?)?????
14. ???????if?(?a%t?==?0?&&?b%t?==0?)????break;??
15. */??

?

[cpp]?view plain?copy

1. //窮舉法求最小公倍數??
2. ?????for?(i=?a;?;?i++?)??
3. ?????????if?(?i?%?a?==?0?&&?i?%?b?==0?)?????break;??
4. ?????printf("The?least?common?multiple:%d\n",?i?)??
5. ???
6. //多個數的最大公約數和最小公倍數??
7. ?????for?(i=?a;?i>0;?i--?)??
8. ?????????if?(a%i==0&&b%i==0&&c%i==0)?????break;??
9. ?????printf("The?largest?common?divisor:%d\n",?i);??
10. ?????for?(i=?a;?;?i++?)??
11. ?????????if?(i%a==0&&i%b==0&&i%?c==0)????break;??
12. ?????printf("The?least?common?multiple:%d\n",?i?)??
13. ?