c - 最小公因数

Question

谁能建议一些快速的方法来计算给定两个数字的最低公因数（不包括 1）？一种方法是检查 GCD(a,b)>1，素数分解（a 和 b），并选择最小的公共素数作为结果。

他们是更好的方法吗？

示例：LCF(20,30)=2 , LCF(13,39)=13

Answer 1

最后，我认为您不会找到比尝试将这两个数字除以素数更好的方法，直到您找到一个同时除以或达到sqrt(min(a,b))

Answer 2

只需从 2 循环到值 n/2，其中 n 是两个数字中较小的一个。将条件放入给定的循环中 for(int i=2;i<=n/2;i++) if(n%i==0 && m%i==0)break;

i 是您需要的值。