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()