numero che può essere scritta come somma di due quadrati

Question

Dal principio di matematica:

un numero N è esprimibile come somma di 2 caselle se e solo se la fattorizzazione prima di N, ogni primo del modulo (4k+3) si verifica un numero pari di volte!

Quello che ho fatto è precalcolato tutti i numeri 4k+3 e controllarne la frequenza per divisione continua.

Questo programma è scritto in corrispondenza dei vincoli:

1 < T <100 
0 < N < 10^12 

---

import java.util.Scanner; 

public class TwoSquaresOrNot { 
    static int max = 250000; 
    static long[] nums = new long[max]; 

    public static void main(String args[]) { 
     Scanner sc = new Scanner(System.in); 
     int T = sc.nextInt(); 
     for (int i = 0; i < max; ++i) 
      nums[i] = 4 * i + 3; 
     while (T-- > 0) { 
      long n = sc.nextLong(); 
      System.out.println((canWrite(n) ? "Yes" : "No")); 
     } 
    } 

    private static boolean canWrite(long n) { 
     // TODO Auto-generated method stub 
     for (int i = 0; i < nums.length; ++i) {//loop through all the numbers 
      if (nums[i] > n) 
       return true; 
      int count = 0; 
      while (n % nums[i] == 0) { 
       count++; 
       n /= nums[i]; 
      } 
      if (count % 2 != 0)//check for odd frequency 
       return false; 
     } 
     return true; 
    } 
} 

Ma questo non sembra funzionare nel sito SPOJ.

Mi manca qualcosa? O sto facendo qualcosa di sbagliato?

0 è anche considerato in questo.

Some valid cases are: 

1 = 1^2 + 0^2 
8 = 2^2 + 2^2 

Answer 1

MODIFICATO COME PER COMMENTI DELL'OP.

Coppia cose. Primo: se stai cercando la fattorizzazione primaria, puoi fermarti quando sei a> sqrt (n), non devi andare fino a n.

Così il vostro codice dovrebbe diventare qualcosa di simile:

private static boolean canWrite(long n) { 
    // TODO Auto-generated method stub 
    for (int i = 0; i < nums.length; ++i) {//loop through all the numbers 
     //FIRST CHANGE: Sqrt 
     if (nums[i] > Math.sqrt(n)) 
      break; 
     int count = 0; 
     while (n % nums[i] == 0) { 
      //SECOND CHANGE: count as an array 
      count[i]++; 
      n /= nums[i]; 
     } 
    } 
    //SECOND CHANGE: count as an array 
    for (int i=0; i<count.length; i++) { 
     if (count[i] %2 != 0) return false; 
    } 
    return true; 
}