結果

問題 No.8030 ミラー・ラビン素数判定法のテスト
ユーザー nonamae
提出日時 2021-11-04 20:04:04
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
RE  
実行時間 -
コード長 911 bytes
コンパイル時間 151 ms
コンパイル使用メモリ 12,416 KB
実行使用メモリ 16,384 KB
最終ジャッジ日時 2024-10-15 02:09:20
合計ジャッジ時間 26,299 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 8 RE * 1 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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.randrange(1, n - 1)
    if math.gcd(a, n) > 1:
      return False
    j = jacobi_symbol(a, n)
    if j % n != 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