A collection of prime finding algorithms implemented in pure python

!primefinding.py

import math


def sieve_of_atkin(n: int) -> list[int]:
    """The Sieve of Atkin prime finding algorithm, [1]_
    
    References
    ----------
    .. [1] A. O. L. Atkin, D. J. Bernstein, 2003
    """
    if n < 3: return []
    if n < 4: return [2]
    if n < 6: return [2, 3]
    
    m = n + 1
    P = [2, 3]
    
    sieve = [False] * (m)
    sqrtn = math.isqrt(n)

    for x in range(1, sqrtn + 1):
        for y in range(1, sqrtn + 1):
            h = x**2
            k = y**2

            i = 4 * h + k
            
            if i < m and (i % 12 == 1 or i % 12 == 5): sieve[i] = not sieve[i]
            
            i = i - h
            
            if i < m and i % 12 == 7: sieve[i] = not sieve[i]
            
            i = i - 2 * k
            
            if x > y and i < m and i % 12 == 11: sieve[i] = not sieve[i]

    for x in range(5, sqrtn):
        if sieve[x]:
            z = x**2

            for k in range(z, n + 1, z):
                sieve[k] = False

    for x in range(5, n):
        if sieve[x]: P.append(x)

    return P


def sieve_of_eratosthenes(n: int) -> list[int]:
    """The Sieve of Eratosthenes prime finding algorithm, [1]_

    References
    ----------
    .. [1] Nicomachus of Gerasa, 2nd c. AD
       Introduction to Arithmetic
    """
    sieve = [True] * (n + 1)
    sqrtn = math.isqrt(n)

    for x in range(2, sqrtn + 1):
        if sieve[x]:
            for i in range(x * x, n + 1, x):
                sieve[i] = False

    return [x for x in range(2, n) if sieve[x]]


def segmented_sieve_of_eratosthenes(n: int) -> list[int]:
    """The page-segmented Sieve of Eratosthenes prime finding algorithm, [1]_
    
    Notes
    -----
    The algorithm trades time efficiency for space efficiency to the non-segmented algorithm.
    
    References
    ----------
    .. [1] C. Bays, R. H. Hudson, 1977
       The Segmented Sieve of Eratosthenes and Primes in Arithmetic Progressions to 10^12
    """
    shape = math.isqrt(n) + 1
    sieve = [True] * shape
    
    P = []
   
    for x in range(2, shape):
        if sieve[x]:
            P.append(x)

            for i in range(x * x, shape, x):
                sieve[i] = False

    lower = shape

    while lower < n:
        upper = min(lower + shape, n)
        segments = [True] * (upper - lower)
        
        for x in P:
            start = max(x * x, (lower // x) * x)
            
            if start < lower:
                start += x
            
            for i in range(start, upper, x):
                segments[i - lower] = False

        for x in range(lower, upper):
            if segments[x - lower]:
                P.append(x)
                
        lower = upper

    return P


def mixed_sieve(n: int) -> list[int]:
    """prime finding algorithm mixed via rule-of-thumb"""
    if n < 1_000: return sieve_of_atkin(n)
    return sieve_of_eratosthenes(n)

~__main__.py

from tqdm.auto import tqdm

from plotting import plot_measure_efficiency
from primefinding import (
    sieve_of_eratosthenes, 
    segmented_sieve_of_eratosthenes, 
    sieve_of_atkin, 
    mixed_sieve
)
from profiling import measure


def main():
    M = [sieve_of_eratosthenes, segmented_sieve_of_eratosthenes, sieve_of_atkin, mixed_sieve]
    N = list(range(10, 1_000_000_000, 10))
    
    efficiency = {closure.__name__: {"elapsed": [], "space": []} for closure in M}
    
    for n in tqdm(N, desc="prime finding"):
        for closure in M:
            elapsed, space = measure(closure, n)

            efficiency[closure.__name__]["elapsed"].append(elapsed)
            efficiency[closure.__name__]["space"].append(space)
            
    plot_measure_efficiency(N, efficiency)


if __name__ == "__main__":
    main()

~plotting.py

import typing

import matplotlib.pyplot as plt


class Tracker(typing.TypedDict):
    """elapsed and space efficiency tracker for single configuration"""
    elapsed: list[float]
    space: list[float]


def plot_measure_efficiency(N: list[int], efficiency: dict[str, Tracker]):
    """plots the elapsed and space efficiency of multiple configurations"""
    plt.figure(figsize=(12, 6))

    plt.subplot(1, 2, 1)
    
    for config in efficiency:
        plt.plot(N, efficiency[config]["elapsed"], label=config)

    plt.xlabel("upper limit")
    plt.ylabel("elapsed (s)")
    plt.xscale("log")
    plt.yscale("log")
    plt.legend()
    plt.title("elapsed efficiency")

    plt.subplot(1, 2, 2)
    
    for config in efficiency:
        plt.plot(N, efficiency[config]["space"], label=config)

    plt.xlabel("upper limit")
    plt.ylabel("space (MiB)")
    plt.xscale("log")
    plt.yscale("log")
    plt.legend()
    plt.title("space efficiency")

    plt.tight_layout()
    plt.show()

~profiling.py

import time
import typing
from typing import Any

from memory_profiler import memory_usage


def measure(closure: typing.Callable[..., Any], *args: Any, **kwargs: Any) -> tuple[float, float]:
    """measures the elapsed and space efficiency of a closure"""
    start = time.perf_counter()
    space = memory_usage((closure, args, kwargs), interval=0.1, max_usage=True)
    
    elapsed = time.perf_counter() - start

    return elapsed, space

~requirements.txt

matplotlib
memory-profiler
tqdm