Prime power triples
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?
素数幂三元组
最小的可以表示为一个素数的平方，加上一个素数的立方，再加上一个素数的四次方的数是28。实际上，在小于50的数中，一共有4个数满足这一性质：
28 = 22 + 23 + 24
33 = 32 + 23 + 24
49 = 52 + 23 + 24
47 = 22 + 33 + 24
有多少个小于五千万的数，可以表示为一个素数的平方，加上一个素数的立方，再加上一个素数的四次方？
解题
先求素数，筛选法求素数，题意就是 num = a^2+b^3+c^4 num《五千万，a、b、c都是素数
可以看出，a的值最大可以是sqrt(五千万)，b值得最大值是五千万的立方根，c的最大值是五千万的四次方根
所以素数的个数是：sqrt（五千万）+1
下面就直接暴力求解了
注意主要：
在求 立方 和四次放的时候可能出现越界的情况，long也不可以，所以越界的时候 结果是小于0的，大于五千万的也要考虑的
还有一个就是一个数num 可能有好几种表示的形式，也就是说有重复的情况，，，由于开始没有想到重复的情况，让我看了好久才找出问题的，，题目就是的num的个数，不是求的其分解形式个数，，，所以把符合条件的数放在集合中，最后直接集合大小就是答案了。下面java程序输出结果前一个是没有去重的，后一个是去重后的才是答案的
package Level3; import java.util.ArrayList; import java.util.TreeSet; public class PE087{ static void run(){ int MAX = 50000000; int limit = (int)Math.sqrt(MAX) + 1 ; ArrayList<Integer> prime = getPrime(limit); int count = 0; int size = prime.size(); TreeSet<Long> set = new TreeSet<Long>(); for(int a = 0;a< size;a++){ int tmp1 = prime.get(a); long p1 = tmp1*tmp1*tmp1*tmp1; if(p1> MAX || p1 <0) break; for(int b =0;b<size;b++){ int tmp2 = prime.get(b); long p2 = tmp2*tmp2*tmp2; if(p2> MAX || p2 <0 || p1+p2<0 || p1+p2> MAX) break; for(int c = 0;c<size;c++){ int tmp3 = prime.get(c); long p3 = tmp3*tmp3; if(p3> MAX || p3 <0 || p1+p2+p3<0 || p1+p2+p3> MAX) break; long pp = p1+p2+p3; if(pp <MAX && pp>0 && p1>0 && p2>0 && p3>0){ count++; set.add(pp); // if(pp<50) // System.out.println(p1+" p2:"+p2 +" p3:"+p3+" pp:"+ pp); } } } } System.out.println(count +"..."+set.size()); } // 1139575...1097343 // running time=1s585ms static boolean isPrime(int n){ if(n==2) return true; if(n<2) return false; for(int i=2;i<=Math.sqrt(n);i++) if(n%i==0) return false; return true; } static ArrayList<Integer> getPrime(int limit){ ArrayList<Integer> prime = new ArrayList<Integer>(); boolean isPrime = true; prime.add(2); for(int i=3;i<=limit;i++){ isPrime = true; for(int j=0;j<prime.size();j++){ if(i%prime.get(j) ==0){ isPrime = false; break; } } if(isPrime == true){ prime.add(i); // System.out.println(i); } } return prime; } public static void main(String[] args){ long t0 = System.currentTimeMillis(); run(); long t1 = System.currentTimeMillis(); long t = t1 - t0; System.out.println("running time="+t/1000+"s"+t%1000+"ms"); } }
Python
# coding=gbk import time as time t0 = time.time() def run(): MAX = 50000000 limit = int(MAX**0.5) set={} prime = getPrime(limit) for pi in prime: p1 = pi**4 if p1>MAX:break for pj in prime: p2 = pj**3 if p2>MAX:break for pk in prime: p3 = pk**2 if p3>MAX:break if p1 + p2 + p3 <MAX: set[p1+p2+p3] = 1 print len(set) # 1097343 # running time= 0.729000091553 s def getPrime(limit): prime = [2] isPrime = True for i in range(2,limit): isPrime = True for p in prime: if i%p==0: isPrime = False break if isPrime == True: prime.append(i) return prime run() t1 = time.time() print "running time=",(t1-t0),"s"