伪幸运数
|
若正偶数N是2的幂，或其质因数恰好是连续的素数，就被称其为可接受数。
前十二个可接受数依次是2,4,6,8,12,16,18,24,30,32,36,48。
若N是可接受数，则大于1且能使$N+M$为素数的最小整数M就称为N的伪幸运数。
例如，$N=630$是可接受数（它的质因数是2,3,5,7），在631之后的下一个素数是641，因此，630的伪幸运数是$M=11$。
类似地，16的伪幸运数是3。
找出所有小于$10^9$的可接受数N的伪幸运数，并求其中所有不同的伪幸运数之和。
|
本题难度:
|
解答
|
显然可接受数的数量很少，直接枚举这些数并计算其下一个素数即可。
本题中需要多次计算给定数的下一个素数，为减少码量，直接调用Sympy库中的nextprime函数。
枚举时使用深度优先搜索，记录当前的可接受数n和n中最大的素因子$p_k$，初值为$(2,2)$。
每次先用nextprime函数找出伪幸运数，再将np和$np_{k+1}$中小于$10^9$的压入栈。
最终结果是$2209$。
注：需要调用Sympy库，因此以下代码为Python 3。
from sympy import nextprime
bound=10**9
s=set()
q=[(2,2)]
while q:
n,p=q.pop()
m=nextprime(n)
if m-n==1:
m=nextprime(m)
s.add(m-n)
if n*p < bound:
q.append((n*p,p))
p2=nextprime(p)
if n*p2 < bound:
q.append((n*p2,p2))
print(sum(s))
|
| |
