Skip to content

Codility – common prime divisors

May 16, 2018

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.4

N := 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)
}

common_prime_divisor

Advertisements

From → Uncategorized

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

%d bloggers like this: