結果

問題 No.458 異なる素数の和
コンテスト
ユーザー amowwee
提出日時 2016-12-11 18:47:06
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 1,203 bytes
コンパイル時間 182 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 22,400 KB
最終ジャッジ日時 2024-11-29 03:51:58
合計ジャッジ時間 9,841 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24 WA * 2 TLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

def Eratosthenes(maxNum):
    sieve = list(range(2,maxNum+1))
    result = []
    while sieve:
        prime = sieve[0]
        sieve = [x for x in sieve if x % prime]
        result.append(prime)
    return result
 
N=int(input())
primes = Eratosthenes(N)
pLen = len(primes)

tree = [2] + [0]*(pLen-1)    # binary tree, 2 is first prime
depth = 1    # searching depth
s = 2    # sum of adding elements
result = -1
elements = 1    # numbers of prime numbers now searching



while depth:
    # required at least (result - elements) + 1 elements if update results 
    if depth < pLen and s + sum(primes[depth:depth+max(0,result-elements)+1])  <= N:
        tree[depth] = primes[depth]
        s = s + primes[depth]
        depth = depth + 1
        elements = elements + 1
    else:
        # return to last added element and pop it.
        depth = depth - 1
        while depth:
            if tree[depth]:
                tree[depth] = 0
                s = s - primes[depth]
                depth = depth + 1
                elements = elements - 1
                break
            else:
                depth = depth -1
    if s == N and elements > result:
        result = elements

print(result)
0