結果

問題 No.458 異なる素数の和
ユーザー lam6er
提出日時 2025-03-31 17:30:11
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,670 bytes
コンパイル時間 313 ms
コンパイル使用メモリ 82,460 KB
実行使用メモリ 60,852 KB
最終ジャッジ日時 2025-03-31 17:31:14
合計ジャッジ時間 2,914 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
    primes = [i for i, prime in enumerate(is_prime) if prime]
    return primes, is_prime

def main():
    N = int(input().strip())
    if N < 2:
        print(-1)
        return
    
    # Generate primes up to a large enough value (2*1e4)
    primes_list, is_prime = sieve(20000)
    
    sum_primes = []
    primes_used = []
    current_sum = 0
    for p in primes_list:
        if current_sum + p > N:
            break
        current_sum += p
        sum_primes.append(current_sum)
        primes_used.append(p)
    
    # Check for all possible k from maximum possible down to 1
    for k in range(len(sum_primes), 0, -1):
        sum_k = sum_primes[k-1]
        if sum_k == N:
            print(k)
            return
        d = N - sum_k
        
        # Check condition a: d is a prime and larger than last prime in current sum
        if d > primes_used[k-1] and is_prime[d]:
            print(k + 1)
            return
        
        # Check condition b: find if there is a prime[i] such that prime[i] + d is a prime larger than current last prime
        max_prime_in_k = primes_used[k-1]
        for i in range(k):
            q = primes_used[i] + d
            if q > max_prime_in_k and is_prime[q]:
                print(k)
                return
    
    # Check if N itself is a prime (when k=1 is possible)
    if is_prime[N]:
        print(1)
        return
    
    print(-1)

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