maths.sieve_of_atkin
====================

.. py:module:: maths.sieve_of_atkin

.. autoapi-nested-parse::

   Sieve of Atkin algorithm for finding all prime numbers up to a given limit.

   The Sieve of Atkin is a modern variant of the ancient Sieve of Eratosthenes
   that is optimized for finding primes. It has better theoretical asymptotic
   complexity, especially for large ranges.  This is the basic, non-segmented
   form.

   Time Complexity: O(n / log log n)
   Space Complexity: O(n)

   Reference: https://en.wikipedia.org/wiki/Sieve_of_Atkin



Functions
---------

.. autoapisummary::

   maths.sieve_of_atkin.sieve_of_atkin


Module Contents
---------------

.. py:function:: sieve_of_atkin(limit: int) -> list[int]

   Generate all prime numbers up to a given limit using the Sieve of Atkin.

   The Sieve of Atkin is an optimized version of the Sieve of Eratosthenes.
   It uses a different set of quadratic forms to identify potential primes.

   Args:
       limit: Upper bound for finding primes (inclusive)

   Returns:
       List of prime numbers up to the given limit

   Raises:
       ValueError: If limit is negative

   Examples:
       >>> sieve_of_atkin(30)
       [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
       >>> sieve_of_atkin(10)
       [2, 3, 5, 7]
       >>> sieve_of_atkin(2)
       [2]
       >>> sieve_of_atkin(1)
       []
       >>> sieve_of_atkin(0)
       []
       >>> sieve_of_atkin(-5)
       Traceback (most recent call last):
       ...
       ValueError: -5: Invalid input, please enter a non-negative integer.