is_prime64

ソースコード

from titan_pylib.math.is_prime64 import is_prime64

view on github

展開済みコード

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

仕様

is_prime64(n: int) → bool[source]