# Codility – common prime divisors

Algorithm:

For each pair of numbers in the list:

1) First find the GCD of the given pair of numbers

2) Do some boundary checks like at least one number greater than 1 and also GCD greater than 1 (Note GCD of 1 denotes, that there are no common prime divisors)

3) Now take the remainder of each number by dividing by GCD.

4) Take the GCD of the remainder with the GCD got in step 1. If the new GCD is 1 then discard this pair, as it shows no common divisors.

Logic: The GCD is of the form p1^x1*p2^x2…pn^xn, for prime numbers p1 through pn, and x1..xn are in the set [1…Z], Z is greater than 1. So if we get a remainder, which does not share a single prime number with the GCD1 then, it means the prime divisors are not the same of the two numbers.

5) If all stages pass increment the result count, as by now we are sure that the two given numbers have the same prime divisors.

package main

// you can also use imports, for example:

import “fmt”// import “os”

import “math”// you can write to stdout for debugging purposes, e.g.

// fmt.Println(“this is a debug message”)func Solution(A []int, B []int) int {

// write your code in Go 1.4N := len(A)

ret := 0

for_label:

for i := 0; i min_ab {

continue

}if gcd1 == 1 && min_ab > 1 {

continue

}arem := a / gcd1

for arem > 1 {

gcd2 := gcd(arem, gcd1)

if gcd2 == 1 {

continue for_label

}

arem /= gcd2

}

brem := b / gcd1

for brem > 1 {

gcd2 := gcd(brem, gcd1)

if gcd2 == 1 {

continue for_label

}

brem /= gcd2

}

fmt.Printf(“a: %v, b: %v\n”, a, b)

ret++

}return ret

}// Greatest common divisor

func gcd(a, b int) int {

if a == b {

return a

} else if a > b {

if a%b == 0 {

return b

}

return gcd(a%b, b)

} else {

if b%a == 0 {

return a

}

return gcd(a, b%a)

}

}func main() {

var A []int

var B []int

for i := 1; i < 71; i++ {

for j := 1; j < 71; j++ {

A = append(A, i)

B = append(B, j)

}

}fmt.Printf("No. of pairs: %v\n", len(A))

ret := Solution(A, B)

fmt.Printf("Result: %v\n", ret)

}