# Codility ‘CommonPrimeDivisors’ Solution

##### Short Problem Definition:

Check whether two numbers have the same prime divisors.

CommonPrimeDivisors

##### Complexity:

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

expected worst-case space complexity is O(1)

##### Execution:

I will post an explaining image soon!

##### Solution:
```def gcd(p, q):
if q == 0:
return p
return gcd(q, p % q)

def hasSameFactors(p, q):
if p == q == 0:
return True

denom = gcd(p,q)

while (p != 1):
p_gcd = gcd(p,denom)
if p_gcd == 1:
break
p /= p_gcd
else:
while (q != 1):
q_gcd = gcd(q,denom)
if q_gcd == 1:
break
q /= q_gcd
else:
return True

return False

def solution(A, B):
if len(A) != len(B):
raise Exception("Invalid input")
cnt = 0
for idx in xrange(len(A)):
if A[idx] < 0 or B[idx] < 0:
raise Exception("Invalid value")
if hasSameFactors(A[idx], B[idx]):
cnt += 1

return cnt
```

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

• Joseph

I would appreciate the explanation of this code. Could you just describe what are the steps?
Thanks

• I will explain the code with 2 examples. One that returns true and one that returns false.

For the true one. I.e.: 50 an 100 – their factors are (5x5x2) and (5x5x2x2) therefore they have the same factors (not the same count of them but the set of those would be equal).

If you are not familiar with GCD, please read how it is computed on Codility tutorial, I will assume you know what the method does.

The GCD of 50 and 100 is 50.

while (p != 1):

p_gcd becomes 50 -> p becomes 1 -> we break and get into the else flow
while (q != 1):
q_gcd(100, 50) is 50 -> 100/50 = 2
q_gcd(2,50) is 2 -> 2/2 = 1 -> break and get else
-> return TRUE

The false version i.e. 6(2×3) and 9(3×3)
gcd(9,6) is 3

while (p != 1):
p_gcd(3, 6) becomes 3, for p 6/3 -> 2
p_gcd(3, 2) -> 1, which breaks the loop and returns FALSE

In other words, the remaining factors after gcd(p,q) must be the same as the factors of gcd. Which is true for 50 and 100 (gcd(50,100) is (5x5x2) and the remaining ones are 1 and 2). But not true for for 6 and 9 (gcd(6,9) is (3) and the remaining ones are 2 and 3.

It is hard to explain… Please ask, if something is unclear. We might figure out a nice explanation ðŸ™‚