Как уменьшить время выполнения функции

Question

В этом коде я хотел решить задачу Project Euler №3. Цель состоит в том, чтобы найти самое большое простое число. Мой код работает правильно, но во время выполнения есть проблема. Как уменьшить время выполнения? Может ли кто-нибудь предложить какие-либо советы?

public class Euler3 { 

    //https://www.hackerrank.com/contests/projecteuler/challenges/euler003 
    public static void main(String[] args) { 

     long[] inputs = readInputs(); 

     for (int i = 0; i < inputs.length; i++) { 

      System.out.println(findBiggestPrime(inputs[i])); 
     } 

    } 

    public static boolean isPrime(long num) { 

     if (num == 2) 
      return true; 

     for (long i = 3; i * i <= num; i += 2) { 

      if (num % i == 0) 
       return false; 

     } 

     return true; 
    } 

    private static long[] readInputs() { 

     Scanner scanner = new Scanner(System.in); 
     int inputQuantities = scanner.nextInt(); 

     long[] inputs = new long[inputQuantities]; 

     for (int i = 0; i < inputQuantities; i++) { 

      inputs[i] = scanner.nextLong(); 
     } 
     return inputs; 
    } 

    private static long findBiggestPrime(long number) { 

     long biggestPrime = 0; 

     if (number % 2 == 0) { 

      number = number/2; 
      biggestPrime = 2; 
     } 

     if (number == 2) 
      return 2; 



     for (int i = 3; i <= number; i += 2) { 

      if (number % i != 0) 
      continue; 

      if(!isPrime(i)) 
       continue;; 

       biggestPrime = i; 
       number = number/biggestPrime; 

     } 


     return biggestPrime; 
    } 


} 

Answer 1

Линии

if(!isPrime(i)) 
    continue; 

замедлит ваш алгоритм и там не должно быть.

Любой фактор, с которым вы сталкиваетесь в своем алгоритме, должен автоматически быть простым. Вы не должны, например, когда-либо сталкиваться с фактором 15, потому что вы должны были уже встречаться 3 и 5 и делиться ими обоими.

Для выполнения этой работы вы не должны просто делать number = number/biggestPrime;. Когда вы сталкиваетесь с фактором, вы должны продолжать делиться им, пока он больше не войдет в число. Таким образом, вы очищаете полномочия.

Answer 2

isPrime() чрезвычайно неэффективен. Вот версия, которая отслеживает уже подтвержденные-кратные в HashSet. Я не знаю, какой порядок величины вы используете. Это, похоже, работает с некоторой эффективностью на моей машине в диапазоне ~ 100K.

private static final Set<Long> multiples = new HashSet<>(); 

private static boolean isPrime(long l) { 
    if(l%2==0 && l>2) 
     return false; 
    if(multiples.contains(l)) 
     return false; 
    double r = Math.sqrt(l); 
    for(long i=3;i<=r;++i) { 
     for (long j = i * 2; j <= l; j += i) { 
      multiples.add(j); 
      if (j == l) { 
       return false; 
      } 
     } 
    } 
    return true; 
}