# Codility 'CountNonDivisible' Solution

Martin Kysel · January 5, 2015

##### Short Problem Definition:

Calculate the number of elements of an array that are not divisors of each element.

CountNonDivisible

##### Complexity:

expected worst-case time complexity is `O(N\*log(N))`

expected worst-case space complexity is `O(N)`

##### Execution:

Using the Sieve of Eratosthenes, you generate divisors for all input elements of A. If a given number x is a divisor of element (x*N == element), then N also is a divisor. (N = element//x). After all divisors are computed, we simply subtract those (multiplied by their counts or 0) from the total number of elements in A.

##### Solution:
``````
def solution(A):

A_max = max(A)

count = {}
for element in A:
if element not in count:
count[element] = 1
else:
count[element] += 1

divisors = {}
for element in A:
divisors[element] = set([1, element])

# start the Sieve of Eratosthenes
divisor = 2
while divisor*divisor <= A_max:
element_candidate = divisor
while element_candidate  <= A_max:
if element_candidate in divisors and not divisor in divisors[element_candidate]:
element_candidate += divisor
divisor += 1

result = [0] * len(A)
for idx, element in enumerate(A):
result[idx] = (len(A)-sum([count.get(divisor,0) for divisor in divisors[element]]))

return result
``````