c++ - 快速找到两组数字的共同质数

我一直在努力解决这个问题:https://codility.com/programmers/task/common_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。

使用Euclid's Algorithm查找2个数字的GCD。如果是GCD == 1，则答案是false。

请注意，GCD将需要包含两个数字的所有质数才能使答案为真，因此，通过反复将newa = a/GCD和newb = b/GCD除以Euclid(newa, GCD)和Euclid(newb, GCD)，直到newa和newb达到1，才能检查Euclid(newa, GCD)和Euclid(newb, GCD)是否可以减少为1是成功，或者1或ojit_code返回ojit_code，这是失败的。

让我们看看这对于a = 75，b = 15的工作方式:

1)GCD = Euclid(75，15)= 15
2)newa = 75/15 = 5，newb = 15/15 = 1，使用newb完成
3)newa = 5/Euclid(5，15)= 5/5 = 1成功!

a = 6，b = 4怎么样:

1)GCD = Euclid(6，4)= 2
2)newa = 6/2 = 3，newb = 4/2 = 2
3)Euclid(newa，2)= Euclid(3，2)= 1失败!

a = 2，b = 16怎么样

1)GCD = Euclid(2，16)= 2
2)newa = 2/2 = 1(很好)，newb = 16/2 = 8
3)newb = 8/Euclid(8，2)= 8/2 = 4
4)newb = 4/Euclid(4，2)= 4/2 = 2
5)newb = 2/Euclid(2，2)= 2/2 = 1成功!