Paul Erdos Conjecture [Java]

Question

Я пытался решить эту довольно легкую проблему на SPOJ: http://www.spoj.com/problems/HS08PAUL/.

Для этого требуется количество простых чисел (меньше n), которое может быть выражено в виде x^2 + y^4 (где x и y - целые числа).

Я взломал решение грубой силы, которое занимает некоторое время (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

Сколько чисел вида x^2 + y^4 находятся ниже 1000000? Сколько простых чисел ниже 1000000? Что эти два номера говорят вам о том, как вы должны подходить к решению?

комментарий @ isnot2bad также уместен.