結果

問題 No.3030 ミラー・ラビン素数判定法のテスト
ユーザー shop_oneshop_one
提出日時 2020-05-30 00:05:22
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
WA  
実行時間 -
コード長 886 bytes
コンパイル時間 101 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 18,084 KB
最終ジャッジ日時 2024-11-18 17:59:35
合計ジャッジ時間 38,330 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 31 ms
11,136 KB
testcase_01 AC 33 ms
11,136 KB
testcase_02 AC 33 ms
11,136 KB
testcase_03 AC 31 ms
11,136 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 TLE -
権限があれば一括ダウンロードができます

ソースコード

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