結果

問題 No.458 異なる素数の和
ユーザー amowweeamowwee
提出日時 2016-12-11 18:47:06
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
TLE  
実行時間 -
コード長 1,203 bytes
コンパイル時間 329 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 22,016 KB
最終ジャッジ日時 2024-05-06 18:40:30
合計ジャッジ時間 5,015 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 27 ms
22,016 KB
testcase_01 AC 77 ms
11,136 KB
testcase_02 AC 688 ms
11,264 KB
testcase_03 AC 44 ms
10,752 KB
testcase_04 AC 41 ms
10,880 KB
testcase_05 TLE -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
権限があれば一括ダウンロードができます

ソースコード

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