Source code for titan_pylib.math.is_prime64


[docs]
 1def is_prime64(n: int) -> bool:
 2    # assert 1 <= n and n <= 1<<64 # = 18446744073709551616
 3    if n == 1:
 4        return False
 5    if n == 2:
 6        return True
 7    if not n & 1:
 8        return False
 9    p = (
10        (2, 7, 61)
11        if n < 1 << 30
12        else (2, 325, 9375, 28178, 450775, 9780504, 1795265022)
13    )
14    d = n - 1
15    d >>= (d & -d).bit_length() - 1
16    for a in p:
17        if n <= a:
18            break
19        t = d
20        y = pow(a, t, n)
21        while t != n - 1 and y != 1 and y != n - 1:
22            y = y * y % n
23            t <<= 1
24        if y != n - 1 and not t & 1:
25            return False
26    return True