### 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?

### 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