結果

問題 No.458 異なる素数の和
ユーザー compass19compass19
提出日時 2016-12-09 01:10:02
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
RE  
実行時間 -
コード長 1,139 bytes
コンパイル時間 160 ms
コンパイル使用メモリ 12,544 KB
実行使用メモリ 10,752 KB
最終ジャッジ日時 2024-05-06 09:53:12
合計ジャッジ時間 1,838 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

from math import sqrt
from tqdm import tqdm
N = int(input())

def is_prime(n, primes):
	for prime in primes:
		if n/prime == n//prime:
			return False
	else:
		return True

primes = [2]
sum_primes = [2]
_sum = 2
for i in range(3, N+1, 2):
	if is_prime(i, primes):
		primes.append(i)
		_sum += i
		sum_primes.append(_sum)

hash_keys = [list() for _ in range(60403)]

def hash_func(n):
	return n%60403


data = dict()
keys = list()
_len = len(primes)
count = 1
for prime, _sum in zip(primes[::-1], sum_primes[::-1]):
	# print('prime: {}, _sum: {}'.format(prime, _sum))
	# print(data)
	if prime not in hash_keys[hash_func(prime)]:
		data[prime] = 1
		hash_keys[hash_func(prime)].append(prime)
	for key in keys:
		if key+prime > N: continue
		if key+_sum < N: continue
		if key+prime not in hash_keys[hash_func(key+prime)]:
			data[key+prime] = data[key] + 1
			hash_keys[hash_func(key+prime)].append(key+prime)
		else:
			data[key+prime] = max(data[key+prime], data[key]+1)
	keys = list(data.keys()).copy()
	count += 1
# for key in data.keys():
# 	print('{} {}'.format(key, data[key]))


if N in data.keys():
	print(data[N])
else:
	print(-1)
0