結果

問題 No.8030 ミラー・ラビン素数判定法のテスト
ユーザー kokoa1046
提出日時 2018-01-29 17:12:49
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,089 ms / 9,973 ms
コード長 1,493 bytes
コンパイル時間 440 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 78,848 KB
最終ジャッジ日時 2024-11-16 23:07:11
合計ジャッジ時間 6,149 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

# coding: utf-8
# Your code here!
# coding: utf-8
# Your code here!
import random
class millerrabin:

    # factor n into a power of 2 times an odd number
    def pow2_factor(n):
        power = 0
        while n % 2 == 0:
            n //= 2
            power += 1
        return power, n

    """ 
    Rabin-Miller primality test
    returning False implies that n is guarenteed composite
    returning True means that n is probably prime
    with a 4 ** -k chance of being wrong
    """ 

    def is_prime(n, k):
        if n==1:
            return False
        if n==2:
            return True
        if n==3:
            return True
        if n==4:
            return False
        r, d = millerrabin.pow2_factor(n - 1)

        """ 
        returns true if a is a valid 'witness' for n
        a valid witness increases chances of n being prime
        an invalid witness guarentees n is composite
        """ 

        def valid_witness(a):
            x = pow(a, d, n)

            if x == 1 or x == n - 1:
                return False

            for _ in range(r - 1):
                x = pow(x, 2, n)

                if x == 1:
                    return True
                if x == n - 1:
                    return False

            return True

        for _ in range(k):
            if valid_witness(random.randrange(2, n - 2)):
                return False

        return True
for i in range(int(input())):
  x = int(input())
  print(x, int(millerrabin.is_prime(x,50)))
0