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

Prime summations 题号:77 难度: 25 中英对照

It is possible to write ten as the sum of primes in exactly five different ways:

7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2

What is the first value which can be written as the sum of primes in over five thousand different ways?

Solution

对于素数$p$,它可以表示所有$i(i\geq p)$,用$p$表示$i$后,还需要用其他素数来表示$i-p$的部分。 用动态规划,设$dp[i]$表示用素数表示$i$的方案数。 那么枚举所有的素数$p$,再枚举$i(i\geq p)$,对答案$dp[i]$的贡献为$dp[i-p]$。 计算完后判断所有的$dp[x]$是否大于5000,若大于则输出x,否则将限制变宽继续。

Code



public final class p77 {
    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 int prime[]=new int[50000];
    static int dp[]=new int [100];
    static public String run(){
    	int cnt=0;
    	for(int i=2;i<100000 && cnt<prime.length;i++){
    		boolean flag=true;
    		for(int j=2;j<=i/j && flag;j++)
    			if(i%j==0) flag=false;
    		if(flag)
    			prime[cnt++]=i;
    	}
    	dp[0]=1;
    	
    	for(int i=0;i<cnt;i++){
    		for(int j=prime[i];j<dp.length;j++){
    			dp[j]+=dp[j-prime[i]];
    		}
    	}
    	for(int i=0;i<dp.length;i++)
    		if(dp[i]>5000) return ""+i;
    	return null;
	}
    
    
    
    
	
}
71
23ms