Solution to Common-Prime-Divisors by codility | Code Says

Solution to Common-Prime-Divisors by codility | Code Says

A prime is a positive integer X that has exactly two distinct divisors: 1 and X. The first few prime integers are 2, 3, 5, 7, 11 and 13.

A prime D is called a prime divisor of a positive integer P if there exists a positive integer K such that D * K = P. For example, 2 and 5 are prime divisors of 20.

You are given two positive integers N and M. The goal is to check whether the sets of prime divisors of integers N and M are exactly the same.

For example, given:

• N = 15 and M = 75, the prime divisors are the same: {3, 5};
• N = 10 and M = 30, the prime divisors aren't the same: {2, 5} is not equal to {2, 3, 5};
• N = 9 and M = 5, the prime divisors aren't the same: {3} is not equal to {5}.

Write a function:

int solution(int A[], int B[], int Z);

that, given two non-empty zero-indexed arrays A and B of Z integers, returns the number of positions K for which the prime divisors of A[K] and B[K] are exactly the same.

For example, given:

    A[0] = 15   B[0] = 75
    A[1] = 10   B[1] = 30
    A[2] = 3    B[2] = 5

the function should return 1, because only one pair (15, 75) has the same set of prime divisors.

Question: https://codility.com/demo/take-sample-test/common_prime_divisors
http://www.martinkysel.com/codility-commonprimedivisors-solution/

def gcd(x, y):

    # Compute the greatest common divisor

    if x%y == 0:

        return y;

    else:

        return gcd(y, x%y)

def hasSamePrimeDivisors(x, y):

    gcd_value = gcd(x, y)   # The gcd contains all

                            # the common prime divisors

    while x != 1:

        x_gcd = gcd(x, gcd_value)

        if x_gcd == 1:

            # x does not contain any more

            # common prime divisors

            break

        x /= x_gcd

    if x != 1:

        # If x and y have exactly the same common

        # prime divisors, x must be composed by

        # the prime divisors in gcd_value. So

        # after previous loop, x must be one.

        return False

    while y != 1:

        y_gcd = gcd(y, gcd_value)

        if y_gcd == 1:

            # y does not contain any more

            # common prime divisors

            break

        y /= y_gcd

    return y == 1

def solution(A, B):

    count = 0

    for x,y in zip(A,B): // if x<0 or y<0 throw ex;

        if hasSamePrimeDivisors(x,y):

            count += 1

    return count

http://www.cnblogs.com/easonliu/p/4463882.html
判断两个数是否有相同的素数约数。首先求出公约数gcd_val，那么gcd_val里应该包含了common prime divisor，下面分别判断a跟b与gcd_val的公约数是不是有自己的非common prime divisor的prime divisor。

1 def gcd(x, y):
 2     # Compute the greatest common divisor
 3     if x%y == 0:
 4         return y;
 5     else:
 6         return gcd(y, x%y)
 7 
 8 def hasSamePrimeDivisors(x, y):
 9     gcd_value = gcd(x, y)   # The gcd contains all
10                             # the common prime divisors
11 
12     while x != 1:
13         x_gcd = gcd(x, gcd_value)
14         if x_gcd == 1:
15             # x does not contain any more 
16             # common prime divisors
17             break
18         x /= x_gcd
19     if x != 1:
20         # If x and y have exactly the same common 
21         # prime divisors, x must be composed by
22         # the prime divisors in gcd_value. So
23         # after previous loop, x must be one.
24         return False
25 
26     while y != 1:
27         y_gcd = gcd(y, gcd_value)
28         if y_gcd == 1:
29             # y does not contain any more 
30             # common prime divisors
31             break
32         y /= y_gcd
33 
34     return y == 1

https://github.com/acprimer/Codility/blob/master/src/Lesson10/CommonPrimeDivisors.java
    public int solution(int[] A, int[] B) {
        int ans = 0;
        for (int i = 0; i < A.length; i++) {
            if (common(A[i], B[i])) {
                ans++;
            }
        }
        return ans;
    }

    private boolean common(int x, int y) {
        int d = gcd(x, y);
        return commonGCD(d, x) && commonGCD(d, y);
    }

    private boolean commonGCD(int x, int y) {
        int d = gcd(x, y);
        while (d != 1) {
            y /= d;
            d = gcd(x, y);
        }
        return x % y == 0;
    }

    private int gcd(int n, int m) {
        int r = n % m;
        while (r != 0) {
            n = m;
            m = r;
            r = n % m;
        }
        return m;
    }
http://codility-lessons.blogspot.com/2015/03/lesson-10-commonprimedivisors.html

int check(int a, int gcd_ab)

{

    //check if all the prime divisors of 'a' can be found

    //in the prime divisors of gcd(a,b).

    int rest = a / gcd_ab;

    

    //if gcd(a, b) % rest == 0, that means all the prime divisors 

    //of 'rest' is included in the prime divisors of gcd(a,b).

    while (gcd_ab % rest != 0){

        int gcd_tmp = gcd(gcd_ab, rest);

        

        //if gcd(a,b) have 1 as the gcd with rest larger,

        //that means 'a / gcd(a,b)' contains some prime divisor that is not

        //found in the prime divisors of gcd(a,b).
        if (gcd_tmp == 1){

            return 0;

        }

        

        rest /= gcd_tmp;

    }

    

    return 1;

}

int solution(int A[], int B[], int Z) 

{

    int cnt = 0;

    

    int i;

    for (i = 0; i < Z; i++){

        int gcd_ab = gcd(A[i], B[i]);

        if (check(A[i], gcd_ab) && check(B[i], gcd_ab)){

            cnt++;

        }

    }

    

    return cnt;

}

http://www.martinkysel.com/codility-commonprimedivisors-solution/
Read full article from Solution to Common-Prime-Divisors by codility | Code Says