結果

問題 No.3030 ミラー・ラビン素数判定法のテスト
ユーザー nonamaenonamae
提出日時 2021-11-04 19:58:16
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
RE  
実行時間 -
コード長 905 bytes
コンパイル時間 136 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 11,392 KB
最終ジャッジ日時 2024-04-23 02:37:40
合計ジャッジ時間 4,349 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

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