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 andn  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<Pair> get_prime_factorization(long number){int prime=2;int number_of_times=0;ArrayList<Pair> list=new ArrayList<Pair>();    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<=Math.sqrt(10000001);i++){    if(array[i]){        for(int j=2;j*i<=10000000;j++){            array[j*i]=false;            }    }}   Scanner input=new Scanner(System.in);int number_of_inputs=input.nextInt();long array_of_inputs[]=new long[number_of_inputs];int number_of_true=0;int number_of_even=0;for(int i=0;i<number_of_inputs;i++){    array_of_inputs[i]=input.nextLong();}for(int i=0;i<array_of_inputs.length;i++){    if(array_of_inputs[i]==1||array_of_inputs[i]==2){        System.out.println(Yes);    }    else if(array.length-1<array_of_inputs[i]&&array[(int)array_of_inputs[i]]==true){        if(array_of_inputs[i]%4==1){            System.out.println(Yes);        }else{            System.out.println(No);        }        if(array_of_inputs[i]==76){        System.out.println( yolo1);        }    }else{        number_of_true=0;        number_of_even=0;    ArrayList<Pair> 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==number_of_even){        System.out.println(Yes);    }else{        System.out.println(No);    }}}}
Sum of two squares
java;optimization;algorithm;primes;mathematics