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

Question Name: CommonPrimeDivisors

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | 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 |

Thank you for explanation.

BTW, this code can be refactored – put copy-pasted block for x_gsd and y_gsd into separate method.

Great idea! Refactored ðŸ™‚

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

Because I did removeCommonPrimeDivisors mannually twice in hasSamePrimeDivisors ðŸ™‚

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!

Even though 1 is not a prime number, 1 and 1 share the same prime divisors (empty set), right?

Python version:

Thank you so much, now I understood this problem and solve it.

You are very welcome!

LEGEND

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