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

Prime power triples 题号:87 难度: 20 中英对照

The smallest number expressible as the sum of a prime square, prime cube, and prime fourth power is 28. In fact, there are exactly four numbers below fifty that can be expressed in such a way:

28 = 22 + 23 + 24
33 = 32 + 23 + 24
49 = 52 + 23 + 24
47 = 22 + 33 + 24

How many numbers below fifty million can be expressed as the sum of a prime square, prime cube, and prime fourth power?

Solution

先找出所有10000以内的素数,然后三层循环枚举三个素数(这里枚举的上限根据素数的次方的增大而降低),直接计算答案并将其做上标记,最后循环一次把所有有标记的数计数即可。

Code


public final class p87 {
    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 LIMIT=50000000;
    static public int prime[]=new int[10000],prime_cnt=0;
    static public boolean vis[]=new boolean[LIMIT+1];
    
    static public String run(){
    	getPrime();
    	for(int i=0;prime[i]<=7071;i++){
    		for(int j=0;prime[j]<=386;j++){
    			for(int k=0;prime[k]<=84;k++){
    				int tmp=pow(prime[i],2)+pow(prime[j],3)+pow(prime[k],4);
    				if(tmp<=LIMIT)
    					vis[tmp]=true;
    			}
    		}
    	}
    	int ans=0;
    	for(int i=1;i<=LIMIT;i++){
    		if(vis[i])
    			ans++;
    	}
    	return Integer.toString(ans);
    }
    static public void getPrime(){
    	//最普通的列举素数即可
    	for(int i=2;i<10000;i++){
    		boolean flag=true;
    		for(int j=2;j*j<=i;j++){
    			if(i%j==0){
    				flag=false;
    				break;
    			}
    		}
    		if(flag) prime[prime_cnt++]=i;
    	}
    }
    static public int pow(int a,int n){
    	int res=1;
    	while(n-->0) res*=a;
    	return res;
    }
}
1097343
66ms