結果

問題 No.8030 ミラー・ラビン素数判定法のテスト
ユーザー shop_one
提出日時 2020-05-30 00:04:27
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 896 bytes
コンパイル時間 608 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 11,264 KB
最終ジャッジ日時 2024-11-18 17:55:59
合計ジャッジ時間 16,089 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 WA * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

import random
import math


def judge_miller(val):
    if(val == 1):
        return False
    if(val == 2):
        return True
    if(val % 2 == 0):
        return False
    for k in range(100):
        a = random.randint(2, min(val-1, 1000))
        if(math.gcd(a, val) != 1):
            return False
        x = int((val - 1)/2)
        is_prime = False
        while(x % 2 == 0):
            m = pow(a, x, val)
            if(m % val == val-1):
                is_prime = True
            x = int(x/2)
        m = pow(a, x, val)
        if(m % val == 1 or m % val == val-1):
            is_prime = True
        if(not is_prime):
            return False
    return True


if __name__ == "__main__":
    x = int(input())
    for i in range(x):
        v = int(input())
        res = judge_miller(v)
        if(res):
            print(str(v)+" 1")
        else:
            print(str(v)+" 0")
0