Solution to Common-Prime-Divisors by codility

Question: https://codility.com/demo/take-sample-test/common_prime_divisors

Question Name: CommonPrimeDivisors

def gcd(x, y):

''' Compute the greatest common divisor.

'''

if x%y == 0:

return y;

else:

return gcd(y, x%y)

def removeCommonPrimeDivisors(x, y):

''' Remove all prime divisors of x, which also exist in y. And

return the remaining part of x.

'''

while x != 1:

gcd_value = gcd(x, y)

if gcd_value == 1:

# x does not contain any more

# common prime divisors

break

x /= gcd_value

return x

def hasSamePrimeDivisors(x, y):

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

# the common prime divisors

x = removeCommonPrimeDivisors(x, gcd_value)

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

y = removeCommonPrimeDivisors(y, gcd_value)

return y == 1

def solution(A, B):

count = 0

for x,y in zip(A,B):

if hasSamePrimeDivisors(x,y):

count += 1

return count

11 Replies to “Solution to Common-Prime-Divisors by codility”

Mikhail Manukhin says:
January 10, 2016 at 2:44 am
Thank you for explanation.
BTW, this code can be refactored – put copy-pasted block for x_gsd and y_gsd into separate method.
- Sheng says:
  January 11, 2016 at 9:53 pm
  Great idea! Refactored 🙂

Why a refactor is necessary here? Didn’t get chance to see your original code though…

#include <cassert>

#include <vector>

using namespace std;

static int gcd(int a, int b)

{

if (a%b == 0)return b;

else return gcd(b, a%b);

}

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

int len = A.size();

assert(len >= 1 && len < 60001 && B.size() == len);

int a, b, c, d = 0, cnt = 0;

for (int i = 0; i < len; ++i)

a = A[i];

b = B[i];

d = gcd(a, b);

while ((c = gcd(a, d)) != 1)

a /= c;

while ((c = gcd(b, d)) != 1)

b /= c;

if (1 == a && 1 == b)

++cnt;

return cnt;

Sheng says:
January 24, 2016 at 9:00 pm
Because I did removeCommonPrimeDivisors mannually twice in hasSamePrimeDivisors 🙂

Kerem Tubluk says:
April 8, 2016 at 12:43 am
This solution has a false positive as does the Codilitytest, ([1],[1]). So in every set of values where 1,1, exists this solution returns the wrong answer.
1 is not a prime number!
- Sheng says:
  April 9, 2016 at 6:44 pm
  Even though 1 is not a prime number, 1 and 1 share the same prime divisors (empty set), right?

Python version:

def gcd(a, b):

if b == 0:

return a

return gcd(b, a % b)

# write your code in Python 2.7

cnt = 0

for i in xrange(len(A)):

a, b = A[i], B[i]

g = gcd(a, b)

while True:

d = gcd(a, g)

if 1 == d:

a /= d

d = gcd(b, g)

b /= d

cnt += 1 if a == 1 and b == 1 else 0

return cnt

Soley says:
January 29, 2017 at 12:05 pm
Thank you so much, now I understood this problem and solve it.
- Sheng says:
  January 31, 2017 at 8:50 pm
  You are very welcome!
Ardi Nusawan says:
February 3, 2018 at 10:06 am
LEGEND
alkologic says:
February 9, 2020 at 1:54 pm
No need to check a,b separately, checking the product is enough, here is my ruby solution:
https://github.com/alkologic/codility/blob/master/common_prime_divisors.rb

11 Replies to “Solution to Common-Prime-Divisors by codility”

Leave a Reply Cancel reply