考虑形如$t(n)=2n^2-1$（$n>1$）的数。

前几个这样的数分别是$7, 17, 31, 49, 71, 97, 127, 161$。

其中只有$49=7\times 7$和$161=7\times 23$不是素数。

对于$n\le 10000$，一共有2202个$t(n)$是素数。

对不超过五千万的n，共有多少个$t(n)$是素数？

本题难度:

解答

注意到若p是$t(n)=2n^2-1$的约数，那么它也是 $$2(kp\pm n)^2-1=2k^2p^2\pm4kpn+2n^2-1,$$ 的约数。

因此基本的思想类似于筛法，从小到大依次遍历$t(n)$，若p是$t(n)$的约数，那么将它所有的幂都从$t(kp\pm n)$中除去。

在实现上，考虑到内存开销，先生成大小为五千万，值全为1的数组d，然后遍历d。

取$p=2n^2-1/d(n)$，只要$p>1$，它就是需要考察的约数，此时取所有形如$m_k=kd\pm n$的数组下标，将$d(m_k)$乘以$2m_k^2-1$中$p$的最高次幂。

特别地，若$d(n)=1$，则说明$t(n)$是素数。

最终结果是$5437849$。

注：以下代码额外打印了进度信息。

target=50000001

d=[1]*target

r=0
n=2
while n < target:
    x=2*n*n-1
    if d[n] < x:
        if d[n]==1:
            r+=1
        p=x/d[n]
        for i in range(p+n,target,p):
            m=2*i*i-1
            y=p
            while m%y==0:
                y*=p
            y/=p
            d[i]*=y
        for i in range(p-n,target,p):
            m=2*i*i-1
            y=p
            while m%y==0:
                y*=p
            y/=p
            d[i]*=y
    if n < 100 or (n < 1000 and n%100==0) or (n < 10000 and n%1000==0) or n%10000==0:print n,"checked"        
    n+=1
    
print r