結果

問題 No.3127 Multiple of Twin Prime
ユーザー nasutarou1341
提出日時 2025-04-25 21:30:56
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 811 ms / 2,500 ms
コード長 3,462 bytes
コンパイル時間 164 ms
コンパイル使用メモリ 82,124 KB
実行使用メモリ 200,672 KB
最終ジャッジ日時 2025-04-25 21:31:32
合計ジャッジ時間 10,645 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

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

P = Prime(10 ** 7 + 1)
PL = P.getPrimeList()

L = []
for i in range(1, len(PL)):
  a = PL[i - 1]
  b = PL[i]
  if a + 2 == b:
    L.append(a * b)

class nibutan:
  @staticmethod
  def nibutan(ok, ng, op):
    while abs(ok - ng) > 1:
      mid = (ok + ng) >> 1
      if op(mid):
        ok = mid
      else:
        ng = mid
    return ok
  @staticmethod
  def lt(L, n):
    """Lのうちn未満の最大の要素"""
    if L[0] >= n: return -1
    def op(mid):
      return L[mid] < n 
    ok = 0
    ng = len(L)
    return nibutan.nibutan(ok, ng, op)

  @staticmethod
  def le(L, n):
    """Lのうちn以下の最大の要素"""
    if L[0] > n: return -1
    def op(mid):
      return L[mid] <= n 
    ok = 0
    ng = len(L)
    return nibutan.nibutan(ok, ng, op)
      
  @staticmethod
  def gt(L, n):
    """Lのうちn超過の最小の要素"""
    if L[-1] <= n: return len(L)
    def op(mid):
      return L[mid] > n 
    ok = len(L) - 1
    ng = -1
    return nibutan.nibutan(ok, ng, op)
      
  @staticmethod
  def ge(L, n):
    """Lのうちn以上の最小の要素"""
    if L[-1] < n: return len(L)
    def op(mid):
      return L[mid] >= n 
    ok = len(L) - 1
    ng = -1
    return nibutan.nibutan(ok, ng, op)

T = int(input())

for _ in range(T):
  N = int(input())
  a = nibutan.le(L, N)
  if a == -1:
    print(a)
  else:
    print(L[a])
0