結果

問題 No.458 異なる素数の和
ユーザー lam6er
提出日時 2025-04-16 15:53:16
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,185 bytes
コンパイル時間 290 ms
コンパイル使用メモリ 81,688 KB
実行使用メモリ 59,936 KB
最終ジャッジ日時 2025-04-16 15:54:12
合計ジャッジ時間 2,323 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math

def sieve(n):
    if n < 2:
        return []
    sieve = [True] * (n + 1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(math.isqrt(n)) + 1):
        if sieve[i]:
            sieve[i*i : n+1 : i] = [False] * len(sieve[i*i : n+1 : i])
    primes = [i for i, is_prime in enumerate(sieve) if is_prime]
    return primes

n = int(sys.stdin.readline())

primes = sieve(n)

if not primes:
    print(-1)
    sys.exit()

sum_primes = []
s = 0
for p in primes:
    s += p
    sum_primes.append(s)
    if s > n:
        break

max_m = 0
for i in range(len(sum_primes)):
    if sum_primes[i] <= n:
        max_m = i + 1
    else:
        break

for m in range(max_m, 0, -1):
    sum_s = sum_primes[m-1]
    if sum_s > n:
        continue
    D = n - sum_s
    if D == 0:
        print(m)
        sys.exit()
    if (sum_s % 2) != (n % 2):
        continue
    if D % 2 != 0:
        continue
    primes_in_m = primes[:m]
    primes_set = set(primes_in_m)
    for p in primes_in_m[1:]:  # Exclude the first prime (2)
        q = p + D
        if q in primes_set:
            continue
        if q in primes:
            print(m)
            sys.exit()

print(-1)
0