# Solution to Count-Non-Divisible by codility

28 Jan

Question Name: CountNonDivisible

### 9 Replies to “Solution to Count-Non-Divisible by codility”

1. Julian says:

I wonder why this exercise is in the “Sieve of Eratosthenes”, since it’s about divisors (as opposed to factors). Related to this, the detected complexity of my 100% solution was

, when it really was

, which I suspect holds for your solution as well. Thoughts?

• Sheng says:

I do not know neither~ But I agree with you about the time complexity.

2. Andrew says:

Here is a solution that uses a prime number sieve that I believe runs in O(n * log n). Unfortunately, the code is much more complex than the neat O(n^3/2) solution posted above.

The idea is to use a sieve to find the smallest prime that divides each number in the input range, from which one can determine the prime factorization of each number in the input range (this method is described in the reading material that accompanies these questions). Given the prime factorization of x, one can obtain a complete list of divisors of x which is used in the same way as your code above.

I’d love to see the author’s intended solution for this question.

• Pierre-Yves says:

I ‘m not sure that A_max = max(A) costs less than it helps, compare to 2 * N, where it’s used.

• Sheng says:

O(2 * N) equals to O(N). Essentially max(A) does not increase the overall complexity.

3. Anu says:

Hi Sheng,
You have a really good solution to all the problems. I always check on your solutions after trying my own. For this particular problem I have a very similar solution to yours but mine is failing for some test cases. If possible can you point me the mistake?

https://codility.com/demo/results/demoB54VPZ-3P6/

• Sheng says:

Sorry, I do not know much about the C#. But you could use “Console.WriteLine(“this is a debug message”);” to print out all the elements of input A. Then you could debug locally and find out the bug.

4. micropentium6 says:

Here goes my dummy solution! I can prove it’s O(NlogN) though. Since the inner loop runs N times, and each run, it has: sqrt(2)*log2, sqrt(3)*log3…sqrt(N)*logN < (sqrt(2)+sqrt(3)+…+sqrt(N))*logN <= NlogN

The solution is ugly. Take a look on how much extra space I took! It's still considered as O(N) though…