3
\$\begingroup\$

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


}



}



}
\$\endgroup\$
1
  • 1
    \$\begingroup\$ clean up your formatting a little bit please \$\endgroup\$
    – Malachi
    Commented Mar 5, 2014 at 19:55

1 Answer 1

6
\$\begingroup\$

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 , 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 < limit; i++) {
        squares[i] = (i + 1) * (i + 1);
    }
    for (int i = limit - 1; 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];
}
\$\endgroup\$
7
  • \$\begingroup\$ Is the binary search method in java including or excluding the fromTo index- in this case the value of i? Also, in the squares array shouldn't you include the value of zero? \$\endgroup\$
    – The Bear
    Commented Mar 5, 2014 at 3:32
  • \$\begingroup\$ The binary-search documentation is clear, it is exclusive of i which may be a problem. As for the square of 0, is zero square? Your call. \$\endgroup\$
    – rolfl
    Commented Mar 5, 2014 at 3:39
  • \$\begingroup\$ Using your method the time limit has exceeded once again \$\endgroup\$
    – The Bear
    Commented Mar 5, 2014 at 4:00
  • \$\begingroup\$ I believe there is a way to do this in sqrt(n) time, but I don't know what it is... \$\endgroup\$
    – The Bear
    Commented Mar 5, 2014 at 4:08
  • 1
    \$\begingroup\$ I might be wrong but if you are to perform a Sieve of Eratosthenes, prime factoring can be really easy : when performing your Sieve, instead of using a array mapping numbers to a boolean (prime or not prime), use an array mapping numbers n to their smallest (prime) factor if not prime, anything else you can detect (0, -1, n, etc) if prime. Then prime factoring takes as many constant time steps as the number of prime factors. \$\endgroup\$
    – SylvainD
    Commented Mar 6, 2014 at 8:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.