题目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

1. # '动态规划，记cnt(i)为和为i的子集个数，显然对于任意数p，有cnt(i+p)=cnt(i+p)+cnt(i)（相同的i+p，可以有不同的i,p组合）
   
2. #'9275262564250418            150.1563
   
3. 
   
4. def getprimearray(n):   #产生质数数组   b=[2,3,5,7,...]
   
5.     m=int((n-1)/2)
   
6.     a=[0 for i in range(0,m+1)]
   
7.     lmt=int((n**0.5)/2)
   
8.     for i in range(1,lmt+1):
   
9.         if a[i]==0:
   
10.             for j in range(i*3+1,m+1,i*2+1):
    
11.                 a[j]=1
    
12.     b=[2*i+1 for i in range(1,m+1) if a[i]==0]
    
13.     b.insert(0,2)
    
14.     return b
    
15. 
    
16. def getprimearraya(n):   #产生数组,当i是质数时，b[i]=0
    
17.     m=int((n-1)/2)
    
18.     a=[0 for i in range(0,m+1)]
    
19.     b=[1 for i in range(0,n+1)]
    
20.     lmt=int((n**0.5)/2)
    
21.     for i in range(1,lmt+1):
    
22.         if a[i]==0:
    
23.             for j in range(i*3+1,m+1,i*2+1):
    
24.                 a[j]=1
    
25.     for i in range(1,m+1):
    
26.      if a[i]==0:
    
27.         b[2*i+1]=0
    
28.     b[2]=0
    
29.     return b
    
30. 
    
31. md = 10 ** 16
    
32. arr = getprimearray(5000)
    
33. nmax = sum(arr)   #全集和
    
34. brr = getprimearraya(nmax)   #判断质数所有的数组。当i是质数时，brr(i)=0
    
35. cnt=[0 for i in range(nmax+1)]  #cnt(i)为和为i的子集个数
    
36. cnt[0] = 1
    
37. s,res = 0,0  #所有质数之和
    
38. for k in range(len(arr)):
    
39.     p = arr[k]
    
40.     for i in range(s,-1,-1):
    
41.         cnt[i + p] = (cnt[i + p] + cnt[i])%md   
    
42.     s = s + p
    
43. for i in range(2,nmax+1):
    
44.     if brr[i]== 0:
    
45.         res=(res+cnt[i])%md
    
46. print(res)

复制代码