二平方和

Question

我试着做一个SPOJ问题，叫做二次平方，在这里，你可以通过把两个正方形相加来检查当前的数字是否可以得到。然而，我收到了一条“超过时限”的信息。

我正在创建一个筛子的埃拉托斯提尼程序。如果n是素数，并且

N≡1 (mod 4)

那么这个数就是关于两个平方和的Fermat定理的两个平方之和。如果这个数不是素数，那么我分解这个数；如果每个素数因子p，其中p%4=3有一个偶数指数，那么这个数就是两个平方的和。

我如何改进算法，使其运行更快，并没有达到时限？

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


}



}



}

Answer 1

您的代码乱七八糟，不遵循任何标准的命名约定，而且缩进使它变得非常困难。

这不值得一读。你得修好它。

但是，既然您已经标记了这个算法，那么让我们看看它。

Eratosthenes的一个正确的筛子是O(n log log n)复杂度算法。

那么，素保理是困难的，缓慢的。它可能至少是O(n)加上更多。

这个算法是错误的..。

简单地计算正方形要简单得多。

考虑一下这个算法：

• 查找输入的平方根的整数值。
• 找出到那个平方根的所有值的平方。
• 扫描该列表，看看是否可以将其中任何一个组合起来以添加到所需的值。
  • 从广场的一端开始
  • 搜索余数以寻找匹配的值。

这将在O(m log m)中操作，其中m是输入的平方根.会很快的。

下面是一些代码：

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