甘肃建设厅网站好了吗,校园电子商务是什么,山东省城建设计院网站,广州建盏工程设计有限公司求最小公倍数算法#xff1a;
最小公倍数两整数的乘积最大公约数
求最大公约数算法#xff1a;
(1)辗转相除法
有两整数a和b#xff1a;
① a%b得余数c
② 若c0#xff0c;则b即为两数的最大公约数
③ 若c≠0#xff0c;则ab#xff0c;bc#xff0c;再回去执行①…求最小公倍数算法
最小公倍数两整数的乘积÷最大公约数
求最大公约数算法
(1)辗转相除法
有两整数a和b
① a%b得余数c
② 若c0则b即为两数的最大公约数
③ 若c≠0则abbc再回去执行①
例如求27和15的最大公约数过程为
27÷15 余1215÷12余312÷3余0因此3即为最大公约数 [cpp] view plain copy
#includestdio.h void main() /* 辗转相除法求最大公约数 */ { int m, n, a, b, t, c; printf(Input two integer numbers:\n); scanf(%d%d, a, b); ma; nb; while(b!0) /* 余数不为0继续相除直到余数为0 */ { ca%b; ab; bc;} printf(The largest common divisor:%d\n, a); printf(The least common multiple:%d\n, m*n/a); } ⑵ 相减法
有两整数a和b
① 若ab则aa-b
② 若ab则bb-a
③ 若ab则a或b即为两数的最大公约数
④ 若a≠b则再回去执行①
例如求27和15的最大公约数过程为
271512( 1512 ) 15123( 123 )
1239( 93 ) 936( 63 )
633( 33 )
因此3即为最大公约数 [cpp] view plain copy
#includestdio.h void main ( ) /* 相减法求最大公约数 */ { int m, n, a, b, c; printf(Input two integer numbers:\n); scanf (%d,%d, a, b); ma; nb; /* a, b不相等大数减小数直到相等为止。*/ while ( a!b) if (ab) aa-b; else bb-a; printf(The largest common divisor:%d\n, a); printf(The least common multiple:%d\n, m*n/a); } ⑶穷举法
有两整数a和b
① i1
② 若ab能同时被i整除则ti
③ i
④ 若 i a(或b)则再回去执行②
⑤ 若 i a(或b)则t即为最大公约数结束
改进
① i a(或b)
② 若ab能同时被i整除则i即为最大公约数
结束
③ i--再回去执行②
有两整数a和b
① i1
② 若ab能同时被i整除则ti
③ i
④ 若 i a(或b)则再回去执行②
⑤ 若 i a(或b)则t即为最大公约数结束
改进
① i a(或b)
② 若ab能同时被i整除则i即为最大公约数
结束
③ i--再回去执行② [cpp] view plain copy
#includestdio.h void main () /* 穷举法求最大公约数 */ { int m, n, a, b, i, t; printf(Input two integer numbers:\n); scanf (%d,%d, a, b); ma; nb; for (i1; i a; i) if ( a%i 0 b%i 0 ) ti; printf(The largest common divisor:%d\n, t); printf(The least common multiple:%d\n, m*n/t); } /* 改进后的 for (t a; t0; 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; i0; i-- ) if (a%i0b%i0c%i0) break; printf(The largest common divisor:%d\n, i); for (i a; ; i ) if (i%a0i%b0i% c0) break; printf(The least common multiple:%d\n, i )
