Codility 34번 CommonPrimeDivisors

CommonPrimeDivisors

 

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:

class Solution { public int solution(int[] A, int[] B); }

that, given two non-empty 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.

Write an efficient algorithm for the following assumptions:

• Z is an integer within the range [1..6,000];
• each element of arrays A, B is an integer within the range [1..2,147,483,647].

  Copyright 2009–2019 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

 

class Solution {
    public int solution(int[] A, int[] B) {
        int ans = 0;
        for(int i=0; i<A.length; i++){
            if(A[i] == B[i]){
                ans++;
            }else{
                int gcd = gcd(B[i], A[i]);
                if(gcd!=1){
                    int k;
                    if(A[i] > B[i]){
                        k = A[i]/gcd;
                    }else{
                        k = B[i]/gcd;
                    }
                    if(k>=gcd){
                        if(k%gcd == 0){
                            ans++;
                        }
                    }else{
                        if(gcd%k == 0){
                            ans++;
                        }
                    }
                }
            }
        }
        return ans;
    }
    
    int gcd(int a, int b){
        if(b == 0){
            return a;
        }
        return gcd(b, a%b);
    }
}