Как я могу оптимизировать этот код JAVA в терминах скорости?

Question

import java.util.Scanner;

public class Problem1 {
    static int T,ans[];
    static long A,B;
    public static void main(String ar[]){
        Scanner scan=new Scanner(System.in);
        T=scan.nextInt();
        ans=new int[T];
        for(int i=0;i<T;i++){
            A=scan.nextLong();
            B=scan.nextLong();
            for(long j=A;j<=B;j++){
                if(getLucky(j)){
                    ans[i]++;
                }
            }
        }
        for(int i=0;i<T;i++){
            System.out.println(ans[i]);
        }
    }
    public static boolean getLucky(long j){
        boolean lucky=false;
        long rem,sum=0,sum1=0;
        while(j>0){
            rem=j%10;
            sum=sum+rem;
            sum1=sum1+(rem*rem);
            j=j/10;
        }
        if(isPrime(sum)&&isPrime(sum1)){
            lucky=true;
        }
        return lucky;
    }
    public static boolean isPrime(long sum){
        boolean status=true;
        if(sum!=1){
            for (int i=2; i < sum ;i++ ){
              int n = (int) (sum % i);
              if (n==0){
                    status=false;
                    break;
              }
            }
        }else{
            status=false;
        }
        return status;
    }
}

Этот код предназначен для задачи, в которой я нахожу общее число между A и B, сумма цифр и сумма квадратов которых простые. Но мне нужно сделать это оптимальным. Как я могу это сделать?

Answer 1

Вы проверяете больше номеров, чем нужно в isPrime.Вам нужно только проверить до sqrt (sum), так как, если сумма факторизована, у нее должен быть хотя бы один фактор <= ее квадратный корень. </p>

public static boolean isPrime(long sum){
    boolean status=true;
    if(sum!=1){
        int limit = Math.sqrt(sum);
        for (int i=2; i <= limit;i++ ){
          int n = (int) (sum % i);
          if (n==0){
                return false;

          }
        }
    }else{
        status=false;
    }
    return status;
}

Есть и другие мелочи, которые я тоже вижу.Как будто вы продолжаете устанавливать логические значения, а затем возвращаете их.Как только вы узнаете, что число не простое, сразу же возвращайтесь.Там нет необходимости устанавливать статус, выйти из цикла и затем вернуться.То же самое для getLucky ().Вместо if(isPrime(sum)&&isPrime(sum1)){ lucky=true; } используйте return isPrime(sum) && isPrime(sum1);

Answer 2

Код оптимизации может быть сложно.Сделать код оптимальным может быть что-то другое.

Есть много подвопросов: оптимизация, с точки зрения скорости / памяти?На каком устройстве?С самого начала или после долгого времени работы?

Но сначала дайте переменной явное имя, потому что A, B, T ничего не значат для меня / другого кода, и более длинное имя переменной не замедлитсяваш код.Во-вторых, использование профилировщика может вам помочь, я обычно использую jvisualvm.exe (в jdk).В-третьих, более быстрый код на вашей машине не обязательно будет быстрее на другом компьютере / устройстве.

В вашем методе getLucky переменная lucky не обязательна, вы можете сделать это: return (isPrime (sum) && isPrime(sum1));

но это сделает ваш код менее читабельным.

В вашем методе isPrime цикл for проверяет, что i является целым числом, а сумма длинным.Поэтому, если сумма больше, чем MAX_INTEGER, у вас будут проблемы.