A number that can be written as the sum of two squares

Question

From the mathematical principle:

A number N is expressed as a sum of 2 squares if and only if in a prime factorization of N every prime number (4k+3) occurs an even number of times!

What I did pre-calculates all 4k+3 numbers and checks its frequency by continuous division.

This program is written in accordance with the restrictions:

 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; } } 

But this does not work on the SPOJ website.

Am I missing something? Or am I doing something wrong?

0 also considered in this.

 Some valid cases are: 1 = 1^2 + 0^2 8 = 2^2 + 2^2 

Answer 1

CONNECTED FOR COMMENT OP.

A couple of things. First: if you are looking for basic factorization, you can stop when you are in> sqrt (n), you do not need to go all the way to n.

So your code should look something like this:

 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; }