简单的深度优先搜索问题，此处用递归的方式实现。
用两个变量s,k分别记录目前已得的数，和当前应处理第k个素数$p_k$（k从0开始计数，即$p_0=2, p_1=3,\ldots$以此类推）。
令a从0开始依次递增，只要$s_a=sp_k^a < 10^9$，就递归处理$s_a$和$k+1$。
初值取$s=1,k=0$，小于100的素数共有25个，因此$k=25$时递归终止并检查所得的数是否超过$10^9$，最后汇总所有符合要求的终止状态即得结果$2944730$。
bound=10**9
p=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
def check(s,k):
if k==25:
return s<=bound
else:
r,t=0,s
while t<=bound:
r+=check(t,k+1)
t*=p[k]
return r
print check(1,0)
|
