Question Name: CommonPrimeDivisors
Solution to Common-Prime-Divisors by codility
def gcd(x, y):
''' Compute the greatest common divisor.
if x%y == 0:
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
x /= gcd_value
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.
y = removeCommonPrimeDivisors(y, gcd_value)
return y == 1
def solution(A, B):
count = 0
for x,y in zip(A,B):
count += 1
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, (,). 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?
Thank you so much, now I understood this problem and solve it.
You are very welcome!
No need to check a,b separately, checking the product is enough, here is my ruby solution: