Paul Erdos 猜想 [Java]

Question

我一直在尝试解决 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) {
        }
    }   
}   

有什么办法可以让这种方法发挥作用吗？

P.S.：请忽略不规则的异常处理。

Answer 1

我使用 bitset 来获取 10^7 以内的所有素数。 生成 x^2 + y^4 直到 10^7 的所有可能值，同时生成每个数字，我检查它是否是素数，然后将其添加到集合中，集合用于获取唯一数字。然后使用 upper_bound 来回答查询。这有点矫枉过正，但我设法用 0.13 秒得到了一个可接受的解决方案。

这是我接受的解决方案。

#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define all(x) begin(x),end(x)
#define v vector
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
const long long inf = 1e7;
bitset<inf>primes;
signed main() {
    fast_io;
    set<int>s;
    s.insert(2);
    primes.set();
    primes[0] = primes[1] = 0;

// Using sieve for getting all primes upto 10^7 
    for (int i = 2; i <= inf; i++) {
        if (primes[i]) {
            for (int j = i * i; j <= inf; j += i)primes[j] = 0;
        }
    }

// generating all the values x^2+y^4 upto 10^7
    for (int i = 0; i * i <= inf; i++)
        for (int j = 0; j * j * j * j <= inf; j++) {
            int value = i * i + j * j * j * j ;
            if (value <= inf and value > 1 and value & 1 and primes[value])s.insert(value);
        }
    v<int>a;
    for (auto i : s)a.push_back(i);
    s.clear();

// answering queries 
    int t; cin >> t;
    while (t--) {
        int n, ans = 0;  cin >> n;
        ans = distance(begin(a), upper_bound(all(a), n));
        cout << ans << '\n';
    }
}

Answer 2

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

@isnot2bad 的评论也很相关。