快速找到两组数字中的普通素数除数

您实际上不必找到数字的素因子来决定它们是否具有相同的素因子.

下面是我想起来了,如果检查一般算法a,并b具有相同的首要因素.这将是比黄金保更快a和b.

如果a == b,答案是true.

如果a == 1 || b == 1,答案是false.

使用欧几里德算法找到2个数的GCD.如果GCD == 1,答案是false.

请注意,GCD将需要包含的答案是正确的所有两个数字的主要因素,所以检查newa = a/GCD和newb = b/GCD可以反复将它们除以减少到1 Euclid(newa, GCD)和Euclid(newb, GCD),直到 newa和newb达到1哪些是成功的,或Euclid(newa, GCD)或Euclid(newb, GCD)退货1这是一个失败.

Let's see how this works for a = 75, b = 15:

1) GCD = Euclid(75, 15) = 15
2) newa = 75/15 = 5, newb = 15/15 = 1, done with newb
3) newa = 5/Euclid(15, 5) = 5/5 = 1 success!

How about a = 6, b = 4:

1) GCD = Euclid(6, 4) = 2
2) newa = 6/2 = 3, newb = 4/2 = 2
3) Euclid(2, newa) = Euclid(2, 3) = 1 fail!

How about a = 2, b = 16:

1) GCD = Euclid(2, 16) = 2
2) newa = 2/2 = 1 (that's good), newb = 16/2 = 8
3) newb = 8/Euclid(2, 8) = 8/2 = 4
4) newb = 8/Euclid(2, 4) = 2
5) newb = 2/Euclid(2, 2) = 1 success!