c++ - 快速找出两组数的公约数

Question

我一直在努力解决这个问题: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;
}

Answer 1

您实际上不必找到数字的质因数来确定它们是否具有相同的质因数。

这是我想出的一个通用算法，用于检查 a 和 b 是否具有相同的质因数。这将比质因数分解 a 和 b 快得多。

1. 如果 a == b，则答案为 true。
2. 如果 a == 1 || b == 1，答案为false。
3. 使用Euclid's Algorithm找到 2 个数字的 GCD。如果 GCD == 1，则答案为 false。
4. 请注意，GCD 需要包含两个数字的所有质因数才能使答案为真，因此请检查 newa = a/GCD 和 newb = b/GCD 可以通过重复将它们除以 Euclid(newa, GCD) 和 Euclid(newb, GCD) 来减少到 1，直到 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(5, 15) = 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(newa, 2) = Euclid(3, 2) = 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(8, 2) = 8/2 = 4
    4) newb = 4/Euclid(4, 2) = 4/2 = 2
    5) newb = 2/Euclid(2, 2) = 2/2 = 1 success!