题目249：素数子集和

欧拉计划

Prime Subset Sums

Let 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 位数字作为你的答案。

grf1973

# '动态规划，记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)