最低公因子

任何人都可以提出一些快速的方法来计算给定的两个数字的最低公因子（不包括1）吗？一种方法可以检查GCD（a，b）> 1，素数因子分解（a和b）以及选择最小的共同素因子作为结果。最低公因子

他们是更好的方法来做到这一点？

例子：LCF（20,30）= 2，LCF（13,39）= 13

来源

2012-06-25 Vineet Deoraj

这功课吗？你有什么尝试？ – unwind

网络上可能有一百万（夸张？...）资源涉及这个话题！请显示你的尝试。 SO不在这里“为你做事”... –

@unwind没有它不是功课。我曾试着用二次方法去做。问题是关于做得更好？ –

最后，我不认为你会发现什么比试图通过素以两个数字除以更好直到你找到一些分开两个或者达到的数字sqrt(min(a,b))

来源

2012-06-25 09:10:35 salva

如果您首先计算'g = gcd（a，b）'，然后搜索'g'的最小素数因子，那么您会得到更好的最坏情况行为。 –

@丹尼尔，对于最糟糕的情况，这是正确的，但对于平均情况下，给定两个随机数字，统计上，它很可能比液晶显示器是一个小数字。所以哑分数方法会比单独计算gcd更快。也许一个混合解决方案，首先检查2,3和5（36％的情况），然后切换到计算gcd并找到它的较小除数（从7开始）将是最好的解决方案。 – salva

我不认为这是非常正确的，也有一个很好的机会，GCD将是1，而这完全毁了忽视GCD的方式。我也认为（除非你对输入有特别的限制，例如没有素数因子<100），首先检查几个小素数，然后做GCD将是平均速度最快的。 –

-1

从2循环到数值n/2，其中n是两个数字中较小的一个。（int i = 2; i < = n/2; i ++） if if（n％i == 0 & & m％i == 0）break;如果给出，

我是你的要求值。

来源

2012-06-25 09:46:09

回答

相关问题