357. 生成素数的整数(Prime generating integers)
\(30\)的因子有\(1,2,3,5,6,10,15,30\)，可以发现对于\(30\)的每个因子\(d\)，\(d+30/d\)都是一个素数。对于不超过\(10^8\)的正整数\(n\)，假设\(n\)的每个因子\(d\)，\(d+n/d\)都是素数，求这样的数\(n\)的和。
分析：这道题的思路比较直接，首先我们可以发现，\(n+1\)需要是一个素数，则我们首先可以求出\(10^8\)以内的所有素数，再把每个数减去一，再从其中筛选符合条件的数。考虑到\(10^8\)以内有素数只有\(5761455\)个，则可以大大缩小筛选的范围。对于这个范围的内的数字，我们逐一检查其互补因子对之和是否是一个素数，如果所有互补因子对都是素数，则是一个符合条件的数。此题的数据规模较大，提升速度的关键是使用更快的素数筛，我借用了\(stackoveflow\)上一个非常快的筛选素数的函数，最终把整道题的执行时间压缩到一分钟以内。代码如下：
# time cost = 32.9 s ± 120 ms
from sympy import isprime
import numpy as np
def prime_sieve(n):
sieve = np.ones(n//3+(n%6==2), dtype=np.bool)
sieve[0] = False
for i in range(int(n**0.5)//3+1):
if sieve[i]:
k=3*i+1|1
sieve[((k*k)//3)::2*k] = False
sieve[(k*k+4*k-2*k*(i&1))//3::2*k] = False
return np.r_[2,3,((3*np.nonzero(sieve)[0]+1)|1)]
def is_valid(n):
u = int(n**0.5) + 1
for i in range(2,u):
if n % i == 0:
if not isprime(i+n//i):
return False
return True
def main(N=10**8):
arr = prime_sieve(N) - 1
return arr[np.vectorize(is_valid)(arr)].sum()