当前位置:首页 » Project Euler » 详细页

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?

Solution

因为p是素数,$n^3+n^2 p=m^3$,所以$n^2(n+p)=m^3$. 所以只能让$n$和$n+p$都为立方数 所以这两个立方数相减的差就是一个素数$p$ 又因为 $$a^3 - b^3 = (a-b)(a^2+ab+b^2)$$ 所以只有当$a-b=1$时,$a^3 - b^3$才可能是一个素数. 所以只需要检查相邻的2个立方数之差是否是素数就可以了. 即 $$(n+1)^3-n^3=3n^2+3n+1$$ 所以这题就变成了只需要检查$3n^2+3n+1$是否是素数就可以了。

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