C编程之最大公约数,最小公倍数

m = b *a；

n = c * a;

所以m和n的最小公倍数就应该是a*b*c啊，那不就是m * n / a，其中m和n是已知的，而a就是那个需要求解的最大公约数。所以就有了下面的代码，

view plaincopy to clipboardprint?

1. 2. 3. 4. 5. 6.

int GetMinCommonMultiple(int m, int n) {

assert(m && n);

return m * n / GetMaxCommonDivide(m, n); }

int GetMinCommonMultiple(int m,{assert(m && n);return m * n / GetMaxCo下面就可以开始最大公约数的求解。其实，关于最大公约数的求解，大家看到的更多是各种捷径，比如说欧几里得法。欧几里得法构思十分巧妙，它利用了m、n和n、m%n之间的最大公约数是相等的这一重要条件，充分利用替换的方法，在 m%n等于0的那一刹那，获得我们的最大公约数。然而，我们平时自己所能想到的方法却不多，下面的方法就是具有典型意义的一种： a） 首先对数据m和n判断大小，小的赋值给smaller，大的赋值给larger b）index索引从2开始到smaller遍历，发现有没有数据可以同时被两者整除，有则更新数据 c）循环结束后，获取最大的公约数 view plaincopy to clipboardprint? 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11.

int GetMaxCommonDivide(int n, int m) {

int index; int smaller; int larger; int value; assert(n && m);

if(n > m){ larger = n; smaller = m;

12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24.

}else{ larger = m; smaller = n; }

value = 1;

for(index = 2; index <= smaller; index++){

if(0 == (smaller % index) && 0 == (larger % index)) value = index; }

return value; }

int GetMaxCommonDivide(int n, i{int index;int smaller;int larger;上面的代码看似没有问题，但是还是留下了一个遗憾，如果m和n的数据都大于32位，那怎么办？也许有的朋友会说，现在有位的cpu。但是如果我们此刻没有位的cpu，那该怎么办呢？ 总结： （1）看似最大公约数、最小公倍数是个小问题，但是要写好不容易，算法、参数判断、逻辑都要注意， （2）如果m和n的数据都比较大，有没有可能利用多核降低计算的复杂度， （3）如果m和n中有数据大于32位，那该怎么办？ （4）小问题看似简单，但是在不同的场景下却可以变得非常复杂，作为面试题可以充分考察面试者的沟通能力和应变能力。