maths.sieve_of_atkin

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

sieve_of_atkin(→ list[int])

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

Module Contents

maths.sieve_of_atkin.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.