Finding common prime divisors in two sets of numbers quickly

Question

I've been trying to crack this problem: https://codility.com/programmers/task/common_prime_divisors/

I have it functioning in terms of returning correct answers but it's incredibly slow for larger numbers, I wanted to see if anyone has a better taken on doing it faster or explaining ways I can optimize it.

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

You do not actually have to find the prime factors of the numbers to decide if they have the same prime factors.

Here is a general algorithm that I thought up for checking if a and b have the same prime factors. This will be much quicker than prime factoring a and b.

1. If a == b, the answer is true.
2. If a == 1 || b == 1, the answer is false.
3. Use Euclid's Algorithm to find the GCD of the 2 numbers. If the GCD == 1, the answer is false.
4. Note that the GCD will need to contain all of the prime factors of both numbers for the answer to be true, so check if newa = a/GCD and newb = b/GCD can be reduced to 1 by repeatedly dividing them by Euclid(newa, GCD) and Euclid(newb, GCD) until newa and newb reach 1 which is success, or Euclid(newa, GCD) or Euclid(newb, GCD) returns 1 which is a fail.

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!