結果

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

ソースコード

diff # 

def sieve(n):
    sieve = [True] * (n + 1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(n**0.5) + 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

def main():
    N = int(input().strip())
    if N < 2:
        print(-1)
        return
    
    max_prime = 2 * N
    primes = sieve(max_prime)
    primes_set = set(primes)
    
    # Precompute the sum of first k primes
    sum_k = []
    current_sum = 0
    for p in primes:
        current_sum += p
        sum_k.append(current_sum)
        if current_sum > N:
            break
    
    max_k = len(sum_k)
    for k in reversed(range(1, max_k + 1)):
        if k > len(sum_k):
            continue
        s = sum_k[k-1]
        if s > N:
            continue
        D = N - s
        if D < 0:
            continue
        first_k = primes[:k]
        first_k_set = set(first_k)
        
        # Check single replacement
        for p in first_k:
            q = p + D
            if q in primes_set and q not in first_k_set:
                print(k)
                return
        
        # Check pair replacement
        for i in range(len(first_k)):
            for j in range(i + 1, len(first_k)):
                p1 = first_k[i]
                p2 = first_k[j]
                required = p1 + p2 + D
                if required > max_prime:
                    continue
                for q1 in primes:
                    if q1 >= required:
                        break
                    if q1 in first_k_set:
                        continue
                    q2 = required - q1
                    if q2 >= q1 and q2 in primes_set and q2 not in first_k_set:
                        print(k)
                        return
    
    print(-1)

if __name__ == "__main__":
    main()
0