0

我一直试图在 SPOJ 上解决这个相当简单的问题：http ://www.spoj.com/problems/HS08PAUL/ 。

它需要找出可以以 x^2+y^4（其中 x 和 y 是整数）的形式表示的素数（小于 n）的数量。

我提出了一个蛮力解决方案，该解决方案占用了相当长的时间（n ~= 1000000），导致引擎抛出 TLE（超出时间限制）错误。这是源代码：

import java.io.*;
import java.util.*;

class HS08PAUL  {
   public static int[] sieve(int n){

        boolean[] prime = new boolean[n+1];
        int[] primeNumbers = new int[n];
        int index = 0;
        Arrays.fill(primeNumbers, 0);
        Arrays.fill(prime,true);

        prime[0] = false;
        prime[1] = false;
        int m = (int)Math.sqrt(n);
        for(int i = 2; i <= m; i++){
            if(prime[i])
            for(int k = i*i; k<=n; k+=i)
                prime[k] = false;

        }

        for(int j = 2; j <= n; j++) {
            if(prime[j]) {
                primeNumbers[index] = j;
                index++;
            }
        }
        return primeNumbers;
    }

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        try{
            double numberOfTestCases = in.nextDouble();
            while(numberOfTestCases -- > 0) {
                int index = 0, y = 0, count = 0;
                int num = in.nextInt();
                int[] primes = sieve(num);
                while(index < num/3 ) {
                    for(y = 1; y < 57   ; y ++) {
                        if(Math.ceil(Math.sqrt(primes[index] - Math.pow(y,4))) == Math.floor(Math.sqrt(primes[index] - Math.pow(y,4)))) {
                                count++;
                                break;
                        }   

                    }
                    index++;
                }
                System.out.println(count);
            }   
        }
        catch(Exception e) {
        }
    }   
}

有没有一种方法可以使这种方法发挥作用？

PS：请忽略不守规矩的异常处理。

4

1 回答 1

-1

1000000以下有多少个x^2+y^4形式的数？1000000以下有多少个质数？这两个数字告诉您应该如何处理解决方案？

@isnot2bad 的评论也很重要。

于 2015-03-22T12:08:14.057 回答