Как ускорить эту программу?

Question

В настоящее время я пытаюсь решить ProjectEuler problem, и у меня все потеряно, кроме скорости. Я почти уверен, что программа выполняется так медленно из-за вложенных циклов. Мне бы хотелось, чтобы некоторые советы о том, как ускорить это. Я новичок программист, поэтому я не знаком с множеством более продвинутых методов/тем.

public class Problem12 { 

    public static void main(String[] args) { 
     int num; 

     for (int i = 1; i < 15000; i++) { 
      num = i * (i + 1)/2; 
      int counter = 0; 

      for (int x = 1; x <= num; x++) { 
       if (num % x == 0) { 
        counter++; 
       } 
      } 
      System.out.println("[" + i + "] - " + num + " is divisible by " + counter + " numbers."); 
     } 
    } 
} 

EDIT: Ниже приведен новый код, который экспоненциально быстрее. Также удалена постоянная печать, чтобы ускорить ее.

public class Problem12 { 

    public static void main(String[] args) { 
     int num; 

     outerloop: 
     for (int i = 1; i < 25000; i++) { 
      num = i * (i + 1)/2; 
      int counter = 0; 

      double root = Math.sqrt(num); 
      for (int x = 1; x < root; x++) { 
       if (num % x == 0) { 
        counter += 2; 
        if (counter >= 500) { 
         System.out.println("[" + i + "] - " + num + " is divisible by " + counter + " numbers."); 
         break outerloop; 
        } 
       } 
      } 
     } 
    } 
} 

Answer 1

Для начала, если смотреть на делителях, вы никогда не должны идти дальше, чем корень квадратный из числа, так как каждый делитель ниже квадратного корня имеет эквивалент выше.

n = a * b => a <= sqrt(n) or b <= sqrt(n) 

Затем вам нужно рассчитывать на другую сторону разделения:

double root = Math.sqrt(num); 
for (int x = 1; x < root; x++) { 
    if (num % x == 0) { 
     counter += 2; 
    } 
} 

квадратный корень является особенным, потому что он считается только один раз, если это целое число:

if ((double) ((int) root) == root) { 
    counter += 1; 
} 

Answer 2

Вы просто необходимо разложить число. p^a * q^b * r^c имеет (a+1)*(b+1)*(c+1) делителей. Вот некоторые основные реализации, используя эту идею:

static int Divisors(int num) { 
    if (num == 1) { 
     return 1; 
    } 

    int root = (int) Math.sqrt(num); 
    for (int x = 2; x <= root; x++) { 
     if (num % x == 0) { 
      int c = 0; 
      do { 
       ++c; 
       num /= x; 
      } while (num % x == 0); 
      return (c + 1) * Divisors(num); 
     } 
    } 

    return 2; 
} 

public static void test500() { 
    int i = 1, num = 1; 
    while (Divisors(num) <= 500) { 
     num += ++i; 
    } 

    System.out.println("\nFound: [" + i + "] - " + num); 
}