結果

問題 No.8114 Prime Checker+1
ユーザー D.F.ナス太郎
提出日時 2025-02-21 13:31:32
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,246 bytes
コンパイル時間 212 ms
コンパイル使用メモリ 82,908 KB
実行使用メモリ 54,784 KB
最終ジャッジ日時 2025-02-21 13:31:35
合計ジャッジ時間 3,115 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 29 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math
class Prime:
  def __init__(self, N: int = 1):
    self.N = N
    self.lpf, self.prime = self.makeLpf(N)
  def getPrimeList(self):
    """素数リスト(Nまで)"""
    return self.prime
  def isPrime(self, x : int):
    """素数判定"""
    if x > self.N: return self.isPrimeBig(x)
    return self.lpf[x] == x
  def primeFactorization(self, x: int):
    """素因数分解"""
    if x > self.N: return self.primeFactrizationBig(x)
    else: return self.primeFactrizationSmall(x)
  def makeLpf(self, N: int):
    """前計算O(N)"""
    lpf = [0] * (N + 1)
    prime = []
    for i in range(2, N + 1):
      if lpf[i] == 0:
        lpf[i] = i
        prime.append(i)
      for p in prime:
        if p > lpf[i]: break
        j = i * p
        if j > N: break
        lpf[j] = p
    return lpf, prime
  def isPrimeBig(self, x):
    """素数判定"""
    if x <= 1: return False
    if x == 2: return True
    if x % 2 == 0: return False
    if x < 4759123141: return self.millerRabin(x, [2, 7, 61])
    return self.millerRabin(x, [2, 325, 9375, 28178, 450775, 9780504, 1795265022])
  def millerRabin(self, n, L):
    """ミラーラビン法"""
    s = 0
    d = n - 1
    while d % 2 == 0:
      s += 1
      d >>= 1
    for a in L:
      if n <= a: return True
      x = pow(a, d, n)
      if x != 1:
        for t in range(s):
          if x == n - 1: break
          x = x * x % n
        else: return False
    return True
  def primeFactrizationSmall(self, x):
    """前計算O(N), クエリO(素因数の数)で素因数分解"""
    p = {}
    while x != 1:
      n = self.lpf[x]
      if n in p: p[n] += 1
      else: p[n] = 1
      x = x // n
    return p
  def primeFactrizationBig(self, x):
    """O(√x)で素因数分解"""
    p = {}
    last = math.floor(x ** 0.5)
    if x % 2 == 0:
      p[2] = 1
      x //= 2
      while x & 1 == 0:
        x //= 2
        p[2] += 1
    for i in range(3, last + 1, 2):
      if x % i == 0:
        x //= i
        p[i] = 1
        while x % i == 0:
          x //= i
          p[i] += 1
    if x != 1:
      p[x] = 1
    return p

N = input()
print(0)
P = Prime(1)
if len(N) <= 18:
  a = int(N)
  if P.isPrime(a):
    print("Yes")
  else:
    print("No")
else:
  print("No")
0