# Codility – count not divisible problem

I like this solution, as it came out simple and elegant. The solution is based on Sieve of Eratosthenes. A variation actually, as had to build only based on numbers available.

package solution

// you can also use imports, for example:

//import “fmt”

// import “os”

//import “sort”

// you can write to stdout for debugging purposes, e.g.

// fmt.Println(“this is a debug message”)

func Solution(A []int) []int {

// write your code in Go 1.4

N := len(A)

mymap := make(map[int]int)

for i := 0; i < N; i++ {

_, ok := mymap[A[i]]

if !ok {

mymap[A[i]] = 1

} else {

mymap[A[i]] += 1

}

}

// construct a custom Eratosthenes sieve

// of factors

// Note we create a custom sieve based on numbers we have

// in the map created above

sieve := make([]int, 2*N+1)

for i := 1; i <= 2*N; i++ {

v, ok := mymap[i]

if ok {

for k := i; k <= 2*N; k += i {

sieve[k] += v

}

}

}

// Now we have every thing computed in the sieve,

// with the help of the sieve.

// We just loop again,

// and return the values from the sive

ret := make([]int, N)

for i := 0; i < N; i++ {

ret[i] = N – sieve[A[i]]

}

return ret

}

And yes, this too got 100% result. Yay!