快速找出两组数的公约数

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

一次（相当微不足道的）优化（更新）：

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;    
}

Answer 2

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

这是我想出的一个通用算法，用于检查 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 是否可以简化为1 通过重复将它们除以 Euclid(newa, GCD) 和 Euclid(newb, GCD) 直到 newa 和 newb 达到 1 即成功，或者 Euclid(newa, GCD) 或 Euclid(newb, GCD) returns 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!

Answer 3

找到很好且非常详细的解释 here:

假设两个数N和M，用质数对它们进行因式分解，然后将N和M的GCD表示为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) 中至少出现一次。

换句话说，如果在(P1, P2, P3, ...Px)中找不到'N/ gcd(N,M)'(N1, N2, N3 ... Ny)的任何质因数，则它不是M的质因数.因此，可以说N和M的质因数集合并不完全相同。

类似地，如果在(P1, P2. P3, ... Px)中找不到'M / gcd(A,B)'(M1, M2, L3 ... Ly)的任何质因数，则它不是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的none出现在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)中。如果没有，我们再做同样的事情。

Answer 4

上述@vacawama 解决方案的python 实现。

def gcd_division(a, b):
    if not a%b:
        return b
    return gcd_division(b, a%b)

def prime_reduce(n, gcd):
    na = n // gcd
    ngcd = gcd_division(na, gcd)
    if na == 1:
        return True # success base case
    elif ngcd == 1:
        return False
    return prime_reduce(na, ngcd)

def solution(A, B):
    Z = len(A)
    result = 0
    for i in range(0, Z):
        a, b = A[i], B[i]
        if a == b:
            result += 1
        else:
            gcd = gcd_division(a, b)
            result += (prime_reduce(a, gcd) and prime_reduce(b, gcd))
    return result

我运行它有以下测试用例。

if __name__ == '__main__':
    test_cases = (
        (1, ([15, 10, 9], [75, 30, 5]) ),
        (2, ([7, 17, 5, 3], [7, 11, 5, 2]) ),
        (2, ([3, 9, 20, 11], [9, 81, 5, 13]) ),
    )
    for expected, args in test_cases:
        got = solution(*args)
        print('result', expected, got)
        assert(expected == got)

100% https://app.codility.com/demo/results/training7KRXR3-FE5/

Answer 5

Java 实现基于的回答：

  class Solution {
    public int solution(int[] A, int[] B) {
        int count = 0;
        for(int i = 0; i < A.length; i++){
            if(A[i] == B[i]) count++;
            else if(A[i] == 1 || B[i] == 1) continue;
            else{
                int GCD = gcd(A[i], B[i]);
                
                if(GCD == 1) continue;
                
                int newA = A[i]/GCD;
                int newB = B[i]/GCD;
                
                if(checkDiv(newA, GCD) && checkDiv(newB, GCD)) count++;
            } 
        }
        
        return count;
    }
    
    public boolean checkDiv(int num, int gcd){
        
        if(num == 1) return true;
        else if(gcd == 1) return false;
        
        else {
            gcd = gcd(gcd, num);
            num = num/gcd;
        
            return checkDiv(num, gcd);
        }
    }
    public int gcd(int a, int b){
        if(b == 0) return a;
        else return gcd(b, a % b);
    }
}

Answer 6

Javascript 使用@vacawama 回答的解决方案。 100% 可食用性


function solution(A, B) {

    function getGcd(a,b, res = 1) {
        if (a === b) return res * a;
        if (a % 2 === 0 && b % 2 === 0) return getGcd(a/2, b/2, 2 * res);
        if (a % 2 === 0) return getGcd(a/2, b, res);
        if (b % 2 === 0) return getGcd(a, b/2, res);
        if (a > b) return getGcd(a-b, b, res);
        else return getGcd(a, b-a, res);
    }

    const hasCommonPrimeDivisors = (a, b) => {
        if (a === b) return true;
        if (a === 1 || b === 1) return false;
        let gcd = getGcd(a, b);
        if (gcd === 1) return false;
        while (a !== 1 || b !== 1) {
            let newGcd;
            if (a !== 1) {
                newGcd = getGcd(a, gcd);
                if (newGcd === 1) {
                    return false;
                }
                a = a / newGcd;
            }

            if (b !== 1) {
                newGcd = getGcd(b, gcd);
                if (newGcd === 1) {
                    return false;
                }
                b = b/newGcd;
            }
        }
        return true;
    }

    let count = 0
    A.forEach((a, index) => {
        const b = B[index];
        if (hasCommonPrimeDivisors(a, b)) {
            count++;
        }
    })
    return count;
}

Answer 7

对于每对（总共 Z 对）数字 A[i]、B[i]，我们的想法是将 A[i] 和 B[i] 与其共享的素数约数集合一起归约。

如果在这个过程结束时，减少的值不都等于1，那么最初组成A[i]和B[i]的素数集是不同的。

这是 python 代码，实现了 O(Z * log(max(A) + max(B))^2) 复杂度（和 O(1) space 复杂度）。 log(max(A) + max(B))^2部分有点难看，但是对应归约操作

def gcd(a, b):
    if a < b:
        r, s = b, a
    else:
        r, s = a, b
    

    while s > 0:
        r = r % s
        r, s = s, r

    return r


def solution(A, B):
    res = 0

    for i in range(len(A)):
        g = gcd(A[i], B[i])  # set of prime divisors common to A[i] and B[i] is "contained" in g
        A[i] = A[i] // g
        B[i] = B[i] // g

        k = gcd(g, A[i])
        while k > 1:
            A[i] = A[i] // k
            k = gcd(g, A[i])

        k = gcd(g, B[i])
        while k > 1:
            B[i] = B[i] // k
            k = gcd(g, B[i])

        if A[i] == 1 and B[i] == 1:
            res += 1
    
    return res

快速找出两组数的公约数

Finding common prime divisors in two sets of numbers quickly

c++

math

optimization

primes