[Codility] 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:

int solution(vector<int> &A, vector<int> &B);

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.

Assume that:

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].

Complexity:

expected worst-case time complexity is O(Z*log(max(A)+max(B))2);

expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).

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

 // you can use includes, for example:

 // #include <algorithm>

 // you can write to stdout for debugging purposes, e.g.

 // cout << "this is a debug message" << endl;

 int gcd(int a, int b) {

     if (a < b) return gcd(b, a);

     return b >  ? gcd(b, a % b) : a;

 }

 bool hasSamePrimeDivisors(int a, int b) {

     int gcd_val = gcd(a, b);

     int gcd_a, gcd_b;

     while (a != ) {

         gcd_a = gcd(a, gcd_val);

         if (gcd_a == ) break;

         a /= gcd_a;

     }

     if (a != ) return false;

     while (b != ) {

         gcd_b = gcd(b, gcd_val);

         if (gcd_b == ) break;

         b /= gcd_b;

     }

     return b == ;

 }

 int solution(vector<int> &A, vector<int> &B) {

     // write your code in C++11

     int cnt = ;

     for (int i = ; i < A.size() && i < B.size(); ++i) {

         if (hasSamePrimeDivisors(A[i], B[i])) ++cnt;

     }

     return cnt;

 }

 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 hasSamePrimeDivisors(x,y):

             count += 1

     return count

巴特西

[Codility] CommonPrimeDivisors

最新文章

热门文章