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

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. 使用欧几里德算法找到2个数的GCD.如果GCD == 1,答案是false.
4. 请注意,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!