結果

問題 No.8114 Prime Checker+1
ユーザー lif4635
提出日時 2025-02-21 15:20:57
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 642 bytes
コンパイル時間 320 ms
コンパイル使用メモリ 82,496 KB
実行使用メモリ 67,788 KB
最終ジャッジ日時 2025-02-21 15:21:02
合計ジャッジ時間 4,347 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19 RE * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

def miller_rabin(num):
    """ 1 <= x < 1<<64 """
    if num < 4: return num > 1
    if not num&1: return False
    
    d, s = num-1, 0
    while not d&1:
        d >>= 1
        s += 1
        
    tests = (2,7,61) if num < 4759123141 else (2,325,9375,28178,450775,9780504,1795265022)
        
    for test in tests:
        if test >= num: return True
        t = pow(test, d, num)
        if 1 < t < num-1:
            for _ in range(s-1):
                t = t*t%num
                if t == num-1: break
            else:
                return False
    return True


n = int(input())
print(0)

print("Yes" if miller_rabin(n) else "No")
0