### Investigating the primality of numbers of the form 2n2-1题号：216 难度： 45 中英对照

Consider numbers t(n) of the form t(n) = 2n2-1 with n > 1.
The first such numbers are 7, 17, 31, 49, 71, 97, 127 and 161.
It turns out that only 49 = 7*7 and 161 = 7*23 are not prime.
For n ≤ 10000 there are 2202 numbers t(n) that are prime.

How many numbers t(n) are prime for n ≤ 50,000,000 ?

### Code

public final class p216 {

private static int LIMIT;

public static void main(String[] args) {
long start = System.nanoTime();
long result = run();
long end = System.nanoTime();
System.out.println( result );
System.out.println (( end - start )/1000000 +"ms");
}

public static long run() {
LIMIT =	50000000;
// 产生整个2*n^2-1的数字序列
long[] sequence = new long[LIMIT + 1];
sequence[0] = sequence[1] = -1;
for (int i = 2; i < sequence.length; i++)
sequence[i] = 2L * i * i - 1;

int count = 0;
for (int i = 2; i < sequence.length; i++) {

long term = sequence[i];
//遍历到下标i时，如果该项sequence[i]的值为t(i)，那么t(i)就是素数，计数加1
if (term == 2L * i * i - 1)
count++;

//以下操作跳过那些下标 j > LIMIT*2的项，在Solution的引理3中说明
if (1 < term && term <= LIMIT * 2) {

//访问后续序列中的特定项，除以它们的因子p
int p = (int)term;

//使用p去除下标满足j mod p = i 的sequence[j]
for (int j = i + p; j < sequence.length; j += p) {

while (sequence[j] % p == 0)
sequence[j] /= p;
}
//使用p去除下标满足j mod p = -i的sequence[j]
for (int j = i + (p - i) * 2 % p; j < sequence.length; j += p) {
while (sequence[j] % p == 0)
sequence[j] /= p;
}
}
}
return count;
}

}

5437849
8462ms