### Prime cube partnership题号：131 难度： 40 中英对照

There are some prime values, p, for which there exists a positive integer, n, such that the expression n3 + n2p is a perfect cube.

For example, when p = 19, 83 + 82×19 = 123.

What is perhaps most surprising is that for each prime with this property the value of n is unique, and there are only four such primes below one-hundred.

How many primes below one million have this remarkable property?

### Code

public final class p131 {
public static void main(String[] args) {
long start=System.nanoTime();
String result = run();
long end=System.nanoTime();
System.out.println(result);
System.out.println( (end-start)/1000000 + "ms" );
}
static public final int N=1000000;
static public boolean isPrime[]=new boolean[N+1];
static public String run(){
isPrime[2]=true;
for(int i=3;i<=N;i++){
isPrime[i]=true;
for(int j=3;j<=i/j && isPrime[i];j+=2)
if(i%j==0)
isPrime[i]=false;
}
int ans=0;
for(int x=1;x*x*3+x*3+1<N;x++)
if(isPrime[x*x*3+x*3+1])
ans++;
return ""+ans;
}
}
173
376ms