結果

問題 No.8030 ミラー・ラビン素数判定法のテスト
ユーザー 👑 Mizar
提出日時 2024-12-18 20:04:14
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,156 ms / 9,973 ms
コード長 3,700 bytes
コンパイル時間 367 ms
コンパイル使用メモリ 82,016 KB
実行使用メモリ 86,244 KB
最終ジャッジ日時 2024-12-18 20:04:22
合計ジャッジ時間 7,437 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""Python: Baillie-PSW素数判定法"""
from typing import Optional
import math
import sys

def issq(n: int) -> bool:
    """平方数判定"""
    if n < 0 or ((0x02030213 >> (n & 31)) & 1) == 0:
        return False
    return pow(math.isqrt(n), 2) == n

def kronecker_symbol(a: int, n: int) -> int:
    """クロネッカー記号 https://en.wikipedia.org/wiki/Kronecker_symbol"""
    if n == 0:
        return int(a in (1, -1))
    j = 1
    if n < 0:
        n = -n
        if a < 0:
            j = -j
    if (n & 1) == 0:
        if (a & 1) == 0:
            return 0
        if ((a + 2) & 5) == 5 and ((n & -n).bit_length() & 1) == 0:
            j = -j
        n >>= (n & -n).bit_length() - 1
    if a < 0:
        a = -a
        if (n & 3) == 3:
            j = -j
    while a != 0:
        b = (a & -a).bit_length() - 1
        if ((n + 2) & 5) == 5 and (b & 1) != 0:
            j = -j
        a >>= b
        if (a & n & 3) == 3:
            j = -j
        a, n = n % a, a
    if n == 1:
        return j
    return 0

def isprime_miller_base2(n: int) -> bool:
    """基底2のミラーラビン擬素数判定"""
    #assert n > 2, 'value must be 3 or greater integer'
    #assert (n & 1) == 1, 'value must be odd integer'
    n1 = n - 1
    s = (n1 & -n1).bit_length() - 1
    d = n1 >> s
    t = pow(2, d, n)
    if t in (1, n1):
        return True
    for _ in range(s - 1):
        t = pow(t, 2, n)
        if t == n1:
            return True
    return False

def isprime_lucas(n: int) -> bool:
    """強いリュカ擬素数判定 https://en.wikipedia.org/wiki/Lucas_pseudoprime#Strong_Lucas_pseudoprimes"""
    #assert n > 2, 'value must be 3 or greater integer'
    #assert (n & 1) == 1, 'value must be odd integer'
    d = lucas_dprobe(n)
    if d is None:
        return False
    q = ((1 - d) >> 2) % n
    k = n + 1
    j = (1 << k.bit_length()) >> 1
    k &= j - 1
    j >>= 1
    u, v, qn = 1, 1, q
    while k != 0:
        u = (u * v) % n
        v = (v * v - (qn + qn)) % n
        qn = (qn * qn) % n
        if (k & j) != 0:
            uu = u + v
            v = (d * u + v) % n
            u = uu + (n & -(uu & 1)) >> 1
            if u >= n:
                u -= n
            v = v + (n & -(v & 1)) >> 1
            qn = (qn * q) % n
            k ^= j
        j >>= 1
    if u == 0 or v == 0:
        return True
    for _ in range(((n + 1) & (~n)).bit_length() - 1):
        u = u * v % n
        v = (v * v - (qn + qn)) % n
        if v == 0:
            return True
        qn = (qn * qn) % n
    return False

def lucas_dprobe(n: int) -> Optional[int]:
    """強いリュカ擬素数判定用の係数決定"""
    #assert n > 2, 'value must be 3 or greater integer'
    #assert (n & 1) == 1, 'value must be odd integer'
    i = 5
    while True:
        if i == n:
            i += 2
        d = i if (i & 3) == 1 else -i
        j = kronecker_symbol(d, n)
        if j == -1:
            return d
        if j == 0 and i < n:
            return None
        if i == 61 and issq(n):
            return None
        i += 2

def isprime(n: int) -> bool:
    """Baillie-PSW素数判定法 https://en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_test"""
    if n < 2 or (n & 1) == 0:
        return n == 2
    return (isprime_miller_base2(n) and isprime_lucas(n))

def __main__():
    """
    yukicoder No.3030 ミラー・ラビン素数判定法のテスト https://yukicoder.me/problems/no/3030
    Mojacoder mizar/素数判定 (64bit) https://mojacoder.app/users/mizar/problems/isprime_64bit
    """
    for _ in range(int(sys.stdin.readline().rstrip())):
        a = sys.stdin.readline().rstrip()
        print(a, int(isprime(int(a))))

__main__()
0