結果

問題 No.8030 ミラー・ラビン素数判定法のテスト
ユーザー nonamae
提出日時 2021-11-04 19:57:29
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 905 bytes
コンパイル時間 384 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 79,584 KB
最終ジャッジ日時 2024-10-15 02:00:01
合計ジャッジ時間 3,830 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 WA * 5 RE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math
import random

def jacobi_symbol(a, n):
  if n < 0 or not n % 2:
    raise ValueError("n should be an odd positive integer")
  if a < 0 or a > n:
    a = a % n
  if n == 1 or a == 1:
    return 1
  if math.gcd(a, n) != 1:
    return 0
  j = 1
  if a < 0:
    a = -a
    if n % 4 == 3:
      j = -j
  while a != 0:
    while a % 2 == 0 and a > 0:
      a >>= 1
      if n % 8 in (3, 5):
        j = -j
    a, n = n, a
    if a % 4 == 3 and n % 4 == 3:
      j = -j
    a %= n
  if n != 1:
    j = 0
  return j

def solovay_strassen(n):
  if n == 2 or n == 3:
    return True
  if n % 2 == 0:
    return False
  for _ in range(40):
    a = random.randint(1, n - 1)
    if math.gcd(a, n) > 1:
      return False
    j = jacobi_symbol(a, n)
    if j != pow(a, (n - 1) >> 1, n):
      return False
  return True

for i in range(int(input())):
  x = int(input())
  print(x, int(solovay_strassen(x)))
0