##### Short Problem Definition:

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

##### Link

##### 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]:
divisors[element_candidate].add(divisor)
divisors[element_candidate].add(element_candidate//divisor)
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
```