Project Euler 87 ：Prime power triples 素数幂三元组

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)

#

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

巴特西

Project Euler 87 ：Prime power triples 素数幂三元组

最新文章

热门文章