skais_mapper.utils.primes

Functions for checking and computing prime numbers.

Functions:

Name	Description
is_prime	An almost certain primality check.
next_prime	Next prime strictly larger than n.

is_prime

is_prime(n: int) -> bool

An almost certain primality check.

Source code in skais_mapper/utils/primes.py

def is_prime(n: int) -> bool:
    """An almost certain primality check."""
    if n < 212:
        return n in SMALL_PRIMES

    for p in SMALL_PRIMES:
        if n % p == 0:
            return False

    # if n is a 32-bit integer (max. int is 2147483647), perform full trial division
    if n <= 2147483647:
        i = 211
        while i * i < n:
            for o in SIEVE_OFFSETS:
                i += o
                if n % i == 0:
                    return False
        return True

    # Baillie-PSW
    # this is technically a probabalistic test, but there are no known pseudoprimes
    if not _is_sprp(n):
        return False
    a = 5
    s = 2
    while _legendre(a, n) != n - 1:
        s = -s
        a = s - a
    return _is_lucas_prp(n, a)

next_prime

next_prime(n: int) -> int

Next prime strictly larger than n.

Source code in skais_mapper/utils/primes.py

def next_prime(n: int) -> int:
    """Next prime strictly larger than n."""
    if n < 2:
        return 2
    # first odd larger than n
    n = (n + 1) | 1
    if n < 212:
        while True:
            if n in SMALL_PRIMES:
                return n
            n += 2

    # find our position in the sieve rotation via binary search
    x = int(n % 210)
    s = 0
    e = 47
    m = 24
    while m != e:
        if SIEVE_INDICES[m] < x:
            s = m
            m = (s + e + 1) >> 1
        else:
            e = m
            m = (s + e) >> 1

    i = int(n + (SIEVE_INDICES[m] - x))
    # adjust offsets
    offs = SIEVE_OFFSETS[m:] + SIEVE_OFFSETS[:m]
    while True:
        for o in offs:
            if is_prime(i):
                return i
            i += o