本帖最后由 永恒的蓝色梦想 于 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=[2,3,5,7,...]
m=int((n-1)/2)
a=[0 for i in range(0,m+1)]
lmt=int((n**0.5)/2)
for i in range(1,lmt+1):
if a[i]==0:
for j in range(i*3+1,m+1,i*2+1):
a[j]=1
b=[2*i+1 for i in range(1,m+1) if a[i]==0]
b.insert(0,2)
return b
def getprimearraya(n): #产生数组,当i是质数时,b[i]=0
m=int((n-1)/2)
a=[0 for i in range(0,m+1)]
b=[1 for i in range(0,n+1)]
lmt=int((n**0.5)/2)
for i in range(1,lmt+1):
if a[i]==0:
for j in range(i*3+1,m+1,i*2+1):
a[j]=1
for i in range(1,m+1):
if a[i]==0:
b[2*i+1]=0
b[2]=0
return b
md = 10 ** 16
arr = getprimearray(5000)
nmax = sum(arr) #全集和
brr = getprimearraya(nmax) #判断质数所有的数组。当i是质数时,brr(i)=0
cnt=[0 for i in range(nmax+1)] #cnt(i)为和为i的子集个数
cnt[0] = 1
s,res = 0,0 #所有质数之和
for k in range(len(arr)):
p = arr[k]
for i in range(s,-1,-1):
cnt[i + p] = (cnt[i + p] + cnt[i])%md
s = s + p
for i in range(2,nmax+1):
if brr[i]== 0:
res=(res+cnt[i])%md
print(res)
|