提出 #64533695

---

ソースコード 拡げる

import sys
input = sys.stdin.readline

M = 10**6
prime = [True]*(M+1)
prime[0] = prime[1] = False
for i in range(2, int(M**0.5)+1):
    if prime[i]:
        for j in range(i*i, M+1, i):
            prime[j] = False
primes = [i for i, prime in enumerate(prime) if prime]

tmp = set()
nprimes = len(primes)
for i in range(nprimes):
    p = primes[i]
    prod_p = p
    a = 1
    while prod_p <= M:
        for j in range(i+1, nprimes):
            q = primes[j]
            prod_q = q
            b = 1
            while prod_p * prod_q <= M:
                X = prod_p * prod_q
                tmp.add(X * X)
                b += 1
                prod_q *= q

            if prod_p * q > M:
                break
        a += 1
        prod_p *= p


tmp = sorted(tmp)

Q = int(input())

ans = []
import bisect
for _ in range(Q):
    A = int(input())
    idx = bisect.bisect_right(tmp, A) - 1
    ans.append(str(tmp[idx]))
sys.stdout.write("\n".join(ans))

提出情報

ジャッジ結果