题目249：素数子集和
Prime Subset SumsLet S = {2, 3, 5, ..., 4999} be the set of prime numbers less than 5000.
Find the number of subsets of S, the sum of whose elements is a prime number.
Enter the rightmost 16 digits as your answer.
题目：
设 S = {2, 3, 5, ..., 4999} 为小于 5000 的素数集合。
求满足所有元素和为素数的 S 子集的数目。
输入最右边 16 位数字作为你的答案。
本帖最后由 永恒的蓝色梦想 于 2020-6-30 18:07 编辑
# '动态规划，记cnt(i)为和为i的子集个数，显然对于任意数p，有cnt(i+p)=cnt(i+p)+cnt(i)（相同的i+p，可以有不同的i,p组合）
#'9275262564250418 150.1563
def getprimearray(n): #产生质数数组 b=
m=int((n-1)/2)
a=
lmt=int((n**0.5)/2)
for i in range(1,lmt+1):
if a==0:
for j in range(i*3+1,m+1,i*2+1):
a=1
b===0]
b.insert(0,2)
return b
def getprimearraya(n): #产生数组,当i是质数时，b=0
m=int((n-1)/2)
a=
b=
lmt=int((n**0.5)/2)
for i in range(1,lmt+1):
if a==0:
for j in range(i*3+1,m+1,i*2+1):
a=1
for i in range(1,m+1):
if a==0:
b=0
b=0
return b
md = 10 ** 16
arr = getprimearray(5000)
nmax = sum(arr) #全集和
brr = getprimearraya(nmax) #判断质数所有的数组。当i是质数时，brr(i)=0
cnt=#cnt(i)为和为i的子集个数
cnt = 1
s,res = 0,0#所有质数之和
for k in range(len(arr)):
p = arr
for i in range(s,-1,-1):
cnt = (cnt + cnt)%md
s = s + p
for i in range(2,nmax+1):
if brr== 0:
res=(res+cnt)%md
print(res)
页:
[1]