Task:

Calculate the number of points with integer coordinates that fall into a circle of radius n.

I decided it this way:

def points(n): count = 0 for i in range(-n, n + 1): for j in range(-n, n + 1): if i * i + j * j <= n * n: count += 1 return count

But this code slows down, and the online check gives a timeout. How can you speed up this code? Maybe through the library? In the local IDE (PyCharm) it also slows down.

  • 2
    Possible duplicate question: Number of points in the circle - AnT
  • It is necessary not to solve, it is necessary to optimize. - Linxusr
  • The link is just enough ideas for optimization. - AnT
  • Under the link there is a mention of the Michner's algorithm, using its complexity we get O (n). - Zergatul

2 answers 2

The code can be optimized, for example, by performing a test on one quarter of a circle, and multiplying by two the number of points (except those that lie on the zero X-axis) to obtain the number of points in a semicircle, and multiplying again by two (except those that lie on the zero Y axis) to get the number of points in a circle.

Or go on the other hand, and perform a test on one quarter of a circle, and if the point is not on the axis, then increase the result by 4, and if on the axis, then by 2, and if at the origin, then by 1.

    Decided as advised by the Mincher algorithm.

     def points(n): n *= n count = 0 divisor = 1 while divisor <= n: count += int(n / divisor) count -= int(n / (divisor + 2)) divisor += 4 return count * 4 + 1
    • ??? This is NOT a Michner algorithm. This is a Gauss decision. - AnT
    • Clear. Wrong. Thank. - Linxusr