結果

問題 No.458 異なる素数の和
コンテスト
ユーザー compass19
提出日時 2016-12-09 01:10:02
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
RE  
実行時間 -
コード長 1,139 bytes
コンパイル時間 240 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 10,752 KB
最終ジャッジ日時 2024-11-28 15:40:35
合計ジャッジ時間 2,013 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 3
other RE * 28
権限があれば一括ダウンロードができます

ソースコード

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