結果

問題 No.458 異なる素数の和
ユーザー amowweeamowwee
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 28 ms
16,000 KB
testcase_01 AC 78 ms
22,400 KB
testcase_02 AC 712 ms
16,512 KB
testcase_03 AC 42 ms
10,624 KB
testcase_04 AC 40 ms
10,880 KB
testcase_05 TLE -
testcase_06 AC 501 ms
11,264 KB
testcase_07 AC 28 ms
10,624 KB
testcase_08 TLE -
testcase_09 AC 37 ms
10,880 KB
testcase_10 AC 27 ms
10,624 KB
testcase_11 AC 192 ms
11,648 KB
testcase_12 AC 26 ms
10,624 KB
testcase_13 WA -
testcase_14 AC 26 ms
10,624 KB
testcase_15 AC 25 ms
10,624 KB
testcase_16 AC 32 ms
10,880 KB
testcase_17 AC 25 ms
10,752 KB
testcase_18 AC 25 ms
10,752 KB
testcase_19 AC 26 ms
10,624 KB
testcase_20 WA -
testcase_21 AC 27 ms
10,624 KB
testcase_22 AC 28 ms
10,752 KB
testcase_23 AC 29 ms
10,624 KB
testcase_24 AC 27 ms
10,752 KB
testcase_25 AC 26 ms
10,496 KB
testcase_26 AC 27 ms
10,496 KB
testcase_27 AC 85 ms
11,008 KB
testcase_28 AC 185 ms
11,520 KB
testcase_29 AC 54 ms
10,752 KB
testcase_30 AC 67 ms
17,952 KB
権限があれば一括ダウンロードができます

ソースコード

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