求最小公倍數算法:
最小公倍數=兩整數的乘積÷最大公約數
求最大公約數算法:
(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
- #include<stdio.h>??
- void?main()???/*??輾轉相除法求最大公約數?*/???
- {???
- ???int?m,?n,?a,?b,?t,?c;??
- ???printf("Input?two?integer?numbers:\n");??
- ???scanf("%d%d",?&a,?&b);??
- ???m=a;???n=b;??
- ???while(b!=0)??/*?余數不為0,繼續相除,直到余數為0?*/???
- ???{?c=a%b;?a=b;??b=c;}??
- ???printf("The?largest?common?divisor:%d\n",?a);??
- ???printf("The?least?common?multiple:%d\n",?m*n/a);??
- }??
?
⑵ 相減法
有兩整數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
- #include<stdio.h>??
- void?main?(?)??/*?相減法求最大公約數?*/??
- {????
- ???int?m,?n,?a,?b,?c;??
- ?? ?printf("Input?two?integer?numbers:\n");??
- ???scanf?("%d,%d",?&a,?&b); m=a;?n=b;???
- ?????/*?a,?b不相等,大數減小數,直到相等為止。*/? ??
- ???while?(?a!=b)???
- ?????????if?(a>b)??a=a-b; ???????
- ?????????else??b=b-a; ??
- ???printf("The?largest?common?divisor:%d\n",?a);??
- ???printf("The?least?common?multiple:%d\n",?m*n/a);??
- }??
?
?
?
⑶窮舉法
有兩整數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
- #include<stdio.h>??
- void?main?()??/*?窮舉法求最大公約數?*/??
- {????
- ???int??m,?n,?a,?b,?i,?t; ??
- ???printf("Input?two?integer?numbers:\n");??
- ???scanf?("%d,%d",?&a,?&b); m=a;??n=b;???
- ???for?(i=1;?i<=?a;?i++)????
- ???????if?(?a%i?==?0?&&?b%i?==0?)????t=i;??
- ???printf("The?largest?common?divisor:%d\n",?t);??
- ???printf("The?least?common?multiple:%d\n",?m*n/t);??
- }???
- /*??改進后的?
- ???for?(t=?a;?t>0;?t--?)?????
- ???????if?(?a%t?==?0?&&?b%t?==0?)????break;??
- */??
?
[cpp]?view plain?copy
- //窮舉法求最小公倍數??
- ?????for?(i=?a;?;?i++?)??
- ?????????if?(?i?%?a?==?0?&&?i?%?b?==0?)?????break;??
- ?????printf("The?least?common?multiple:%d\n",?i?)??
- ???
- //多個數的最大公約數和最小公倍數??
- ?????for?(i=?a;?i>0;?i--?)??
- ?????????if?(a%i==0&&b%i==0&&c%i==0)?????break;??
- ?????printf("The?largest?common?divisor:%d\n",?i);??
- ?????for?(i=?a;?;?i++?)??
- ?????????if?(i%a==0&&i%b==0&&i%?c==0)????break;??
- ?????printf("The?least?common?multiple:%d\n",?i?)??
- ?