fork(1) download 
  1. # -*- coding: utf-8 -*-
  2. import time
  3.  
  4. prs =[]; vh =[]
  5.  
  6. def f1(zn, pi):
  7.     if zn==0:
  8.         print("\t", vh)
  9.         return 1
  10.     rtn = 0
  11.     for i in range(pi, 2019):
  12.         if prs[i] > zn: break
  13.         vh.append(prs[i])
  14.         rtn += f1(zn - prs[i], i)
  15.         vh.pop()
  16.     return rtn
  17.  
  18. def eratos(su): #ふるい
  19.     pr = [True if i&1 else False for i in range(su+10)]
  20.     pr[1], pr[2] = False,True
  21.     sq = int(su**0.5)
  22.     for i in range(3, sq+1, 2):
  23.         if not pr[i] : continue
  24.         for j in range(i*i,su+1,i+i): pr[j] = False
  25.     for i in range(su+1):
  26.         if pr[i]: prs.append(i)
  27.     #print(prs)
  28.  
  29. ## f4mに比べればコンパクトだけど、分かりにくくトリッキーな"配列一つ回し"
  30. def f4(tgt, lpr, mxs):
  31.     dp = [0] *(tgt +10); dp[0] =1
  32.     for i in prs:
  33.         if i > lpr: break
  34.         for j in range(tgt, i*(mxs+1)-1,-1): #減算を先に 後ろからやる
  35.             dp[j] -= dp[j-i*(mxs+1)]
  36.         # 上の2行をカットすれば 3)用のスッキリ解答
  37.         for j in range(i, tgt+1): #加算は減算後で 前から累積する感じ
  38.             dp[j] += dp[j-i]
  39.     return dp[tgt]
  40.  
  41. ## f4よりはわかりやすい(?)が、少し重い"配列二つ回し"
  42. ## nxt=i+1,cur=iに換えてメモリー大食い dp[素数の数][目標数]形式にもできる
  43. def f4m(tgt, lpr, mxs):
  44.     dp = [[0] * (tgt+2 ) for _ in range(2)]
  45.     cur, nxt = 0 , 1
  46.     dp[cur][0] =1
  47.     for i,p in enumerate(prs):
  48.         if p > lpr: break
  49.         for j in range(tgt+1):
  50.             dp[nxt][j] =  dp[cur][j] + (dp[nxt][j-p] if j>=p else 0)  \
  51.                        - (dp[cur][j - p*(mxs+1)]  if j >= p*(mxs+1) else 0)
  52.             #db[i+1][j] = dp[i][j] + dp[i+1][j-p] - dp[i][j-p*(mxs+1)] 要約のみ
  53.         cur, nxt = nxt, cur
  54.     return dp[cur][tgt]
  55.  
  56. ## もっとわかりやすいが、この3重ループで今回の制約(11*201931*2019)は無理
  57. def f4x(tgt, lpr, mxs):
  58.     dp = [0] *(tgt +10); dp[0] =1
  59.     for i in prs:
  60.         if i > lpr: break
  61.         for j in range( tgt,-1,-1):
  62.             for k in range(1, mxs+1):
  63.                 if j+k*i > tgt: break
  64.                 dp[j + k*i] += dp[j]
  65.     return dp[tgt]
  66.  
  67. eratos(2019)
  68. print("1)")
  69. print("   合計 %d 通り" %f1(19, 0))
  70. print("2)\t", f4m(31, 31, 31))
  71. print("3)\t", f4(2019, 2019, 2019))
  72. print("4)\t", f4(201931, 31, 2019))
  73. #print( "\t",  f4m(201931, 31, 2019))
  74.  
  75. print( "\n","-" * 10, " speed test f4?(2019,1500,400) ", "-" * 10)
  76. for i,pg in enumerate([f4, f4m, f4x]):
  77.     t1 = time.time()
  78.     print(pg,"\t->", pg(2019,1500,400))
  79.     print("  %.4fsec" %(time.time() - t1))
  80.  
  81.  
Success #stdin #stdout 1.79s 27688KB
comments (?)
stdin 
Standard input is empty
stdout 
1)
	 [2, 2, 2, 2, 2, 2, 2, 2, 3]
	 [2, 2, 2, 2, 2, 2, 2, 5]
	 [2, 2, 2, 2, 2, 2, 7]
	 [2, 2, 2, 2, 2, 3, 3, 3]
	 [2, 2, 2, 2, 3, 3, 5]
	 [2, 2, 2, 2, 11]
	 [2, 2, 2, 3, 3, 7]
	 [2, 2, 2, 3, 5, 5]
	 [2, 2, 2, 13]
	 [2, 2, 3, 3, 3, 3, 3]
	 [2, 2, 3, 5, 7]
	 [2, 2, 5, 5, 5]
	 [2, 3, 3, 3, 3, 5]
	 [2, 3, 3, 11]
	 [2, 3, 7, 7]
	 [2, 5, 5, 7]
	 [2, 17]
	 [3, 3, 3, 3, 7]
	 [3, 3, 3, 5, 5]
	 [3, 3, 13]
	 [3, 5, 11]
	 [5, 7, 7]
	 [19]
   合計 23 通り
2)	 111
3)	 576202207044176168646563
4)	 13683621769893119094927207253137

 ----------  speed test f4?(2019,1500,400)  ----------
<function f4 at 0x2b30f8b55c80> 	-> 576199462419913237080484
  0.0381sec
<function f4m at 0x2b30f8b55d08> 	-> 576199462419913237080484
  0.1354sec
<function f4x at 0x2b30f8b55d90> 	-> 576199462419913237080484
  1.0224sec
https://ideone.com/OFR7bn
2019と素数
language:
Python 3 (python  3.9.5)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!