Sum of two squares

I'm trying to do a SPOJ problem called twosquares where you check whether the current number can be obtained by adding two squares together. However, I'm getting a "time limit exceeded" message.

I'm creating a Sieve of Eratosthenes program. If the number n is prime and


n ≡ 1 (mod 4)

then the number is a sum of two squares by Fermat's theorem on sums of two squares. If the number is not prime then I prime factorize the number; if each prime factor p where p % 4 = 3 has an even exponent then the number is a sum of two squares.

How could I improve the algorithm so that it runs faster and doesn't reach the time limit?

```
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

class sum_of_two_squares_part2 {

static boolean array[];

static ArrayList get_prime_factorization(long number){
int prime=2;
int number_of_times=0;
ArrayList list=new ArrayList();
while(number!=1){
number_of_times=0;

while(number%prime==0 && array[prime]==true){

number=number/prime;

number_of_times++;
}

if(number_of_times>0){
list.add( new sum_of_two_squares_part2().new Pair(prime,number_of_times));
}

if(prime==2){
prime++;
}else{
prime+=2;
}
}

return list;
}

public class Pair{

int number;
int times;

public Pair(int number, int times){
this.number=number;
this.times=times;
}

}

public static void main(String[] args) {

array = new boolean[10000001];
Arrays.fill(array, true);
array[0]=false;
array[1]=false;

for(int i=2;i list=get_prime_factorization(array_of_inputs[i]);

for(int j=0;j<list.size();j++){
//System.out.println("The value of j is: "+j+"\n and the size of arraylist is "+list.size());
if((list.get(j).number-3)%4==0){
number_of_true++;

if(list.get(j).times%2==0){
number_of_even++;
}
}

}
if(number_of_true=

Your code is a mess, does not follow any standard naming conventions, and the indentation makes it really difficult.

It is not really worth reading. You need to fix it.

But, since you have tagged this algorithm, let's look at that.

A correct Sieve of Eratosthenes is an O(n log log n) complexity algorithm.

Then, prime factoring is hard, and slow. It is probably at least O(n) plus more.

This algorithm is just wrong....

It is much simpler to simply calculate the squares.

Consider this algorithm:

• find the integer-value of the square-root of the input.

• find the squares of all values up to that square-root

• scan that list and see if any of them can be combined to add to the desired value.

• start at the one end of the squares

• search the remainder for a matching value.

This will operate in O(m log m) where m is the square-root of the input.... which will be really fast.

Here's some code:

private static int[] getSquareSums(int input) {
    int limit = (int)Math.sqrt(input);
    int[] squares = new int[limit];
    for (int i = 0; i = 0; i--) {
        int target = input - squares[i];
        int pos = Arrays.binarySearch(squares, 0, i, target);
        if (pos >= 0) {
            return new int[]{squares[i], squares[pos]};
        }
    }
    return new int[0];
}

StackExchange Code Review Q#43469, answer score: 6