結果

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

ソースコード

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(1000):
        a = random.randint(2, val-1)
        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