結果

問題 No.3127 Multiple of Twin Prime
ユーザー urunea
提出日時 2025-05-01 04:04:02
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 818 ms / 2,500 ms
コード長 958 bytes
コンパイル時間 476 ms
コンパイル使用メモリ 82,508 KB
実行使用メモリ 158,220 KB
最終ジャッジ日時 2025-05-01 04:04:14
合計ジャッジ時間 11,527 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def make_twin_prime_products(limit, prod_limit):
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False

    for i in range(2, int(limit**0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, limit + 1, i):
                is_prime[j] = False

    twin_products = []
    for i in range(2, limit - 1):
        if is_prime[i] and is_prime[i+2]:
            prod = i * (i+2)
            if prod > prod_limit:
                break
            twin_products.append(prod)

    return twin_products

MAX_N = 10**14
prime_limit = int((MAX_N)**0.5) + 100
p_L = make_twin_prime_products(prime_limit, MAX_N)

T = int(input())
for _ in range(T):
    N = int(input())
    idx = bisect.bisect_left(p_L, N)
    if idx < len(p_L) and p_L[idx] == N:
        print(N)
    else:
        if idx == 0:
            print(-1)
        elif idx == len(p_L):
            print(p_L[idx - 1])
        else:
            print(p_L[idx - 1])
0