我一直在尝试破解这个问题。https:/codility.comprogrammerstaskcommon_prime_divisors。
我有它的功能，在返回正确的答案，但它是令人难以置信的缓慢的较大的数字，我想看看是否有人有一个更好的采取做得更快或解释的方式，我可以优化它。
bool IsPrime(int number)
{
for (int i = 2; i < number; i++)
{
if (number % i == 0)
{
return false;
}
}
return true;
}
bool GetPrimeFactors(int valueA, int valueB)
{
if(valueA < 0 || valueB < 0)
return false;
int max = sqrt(std::max(valueA, valueB)) + 1;//sqrt(std::max(valueA, valueB));
std::vector<int> factors;
bool oneSuccess = false;
for(int i = 2; i <= max; i++)
{
bool remainderA = valueA % i == 0;
bool remainderB = valueB % i == 0;
if(remainderA != remainderB)
return false;
if(IsPrime(i))
{
//bool remainderA = valueA % i == 0;
// bool remainderB = valueB % i == 0;
if(remainderA != remainderB )
{
return false;
}
else if(!oneSuccess && remainderA && remainderB)
{
oneSuccess = true;
}
}
}
return true;
}
int solution(vector<int> &A, vector<int> &B) {
int count = 0;
for(size_t i = 0; i < A.size(); i++)
{
int valA = A[i];
int valB = B[i];
if(GetPrimeFactors(valA, valB))
++count;
}
return count;
}
实际上，你不必找到数字的质因数来决定它们是否具有相同的质因数。
这里是我想出的一个检查是否有相同质因数的通用算法。a 和 b 有相同的质因子。 这将比质因数分解快得多。a 和 b.
a == b答案是 true.a == 1 || b == 1答案是 false.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 这就是失败。让我们来看看这样做是如何工作的a=75，b=15:1) GCD=Euclid(75，15)=152) newa=7515=5，newb=1515=1，完成newb3) newa=5Euclid(15，5)=55=1成功! 不如a=6，b=4：1）GCD=Euclid(6，4)=22）newa=62=3，newb=42=23）Euclid(2，newa)=Euclid(2，3)=1失败! 怎么样a=2，b=16:1)GCD=Euclid(2，16)=22)newa=22=1(这很好)，newb=162=83)newb=8Euclid(2，8)=82=44)newb=8Euclid(2，4)=25)newb=2Euclid(2，2)=1成功!
一个（相当琐碎的）优化(已更新):
bool IsPrime(int number)
{
if (number % 2 == 0)
{
return (number == 2);
}
int limit = sqrt(number);
for (int i = 3; i <= limit; i += 2)
{
if (number % i == 0)
{
return false;
}
}
return true;
}
找到了很好很详细的解释 此处:
假设两个数字 N 和 M，并将它们因式化为质数，然后表示GCD的 N 和 M 作为 P1 * P2 * P3 * P4 * ... Px (这些都是素数除以 gcd(N,M)). 那么，表示 N / gcd(N,M) 和 M / gcd(N,M) 作为 N1 * N2 * N3 * ... Ny和 M1 * M2 * M3 * ... Mz，分别被它们的质数除数；那么。N 和 M 可以表示为如下。
N = (P1 * P2 * P3 ... Px) * N1 * N2 * N3 * ... Ny
M = (P1 * P2 * P3 ... Px) * M1 * M2 * M3 * ... Mz
由于 (P1 * P2 * P3 ... Px) 是 gcd(N,M)，任何素数除数共 N 和 M 总是至少出现一次 (P1, P2, P3, ... Px).
换句话说，如果''的任何素数除数。N/ gcd(N,M)' (N1, N2, N3 ... Ny) 无独有偶 (P1, P2, P3, ...Px)的质数，它不是 M. 因此，可以说，素数除数集的 N 和 M 不完全相同。
同理，如果''的任何一个素数除数。M / gcd(A,B)' (M1, M2, L3 ... Ly) 无独有偶 (P1, P2. P3, ... Px)的质数，它不是 N 并且可以说是 N 和 M 是不完全一样的。
所以问题只是检查是否有任何的 N1-Ny 和 M1-Mz 不见得 P1-Px.
现在让我们想想这个。让 X = N / gcd(N,M) 并考虑 gcd(gcd(N, M), X).
目前，它将如下。
gcd(N,M): P1 * P2 * P3 ... Px
X : N1 * N2 * N3 ... Ny
如果 gcd(N,M) % X == 0的所有质数除数，那么 X 包括在 gcd(N,M).
如果没有，那么我们计算 gcd(gcd(N,M), X). 如果这两个值的gcd只是1，那就意味着没有一个是 N1-Ny 见于 P1-Px;这意味着该值 N 有一个质数不与 M.
如果gcd大于1，那么我们就计算出 X / gcd(gcd(N,M), X)，并更新 X 与此为下一轮。这意味着我们去掉了一些质数除数的 X构成 gcd(gcd(N,M), X)，并用于下一轮
如果 gcd(N, M) % X == 0 这时，也就是说，所有的质数除数的 X 包括在 gcd(N, M). 如果没有，我们再做同样的事情，如上。