Wie würde ich dieses Programm beschleunigen?

Question

Ich versuche gerade eine ProjectEuler problem zu lösen und ich habe alles außer der Geschwindigkeit runter. Ich bin fast sicher, der Grund, warum das Programm so langsam ausgeführt wird, liegt an den verschachtelten Schleifen. Ich würde gerne Ratschläge bekommen, wie man das beschleunigen kann. Ich bin ein Anfänger Programmierer, so dass ich nicht mit vielen der fortgeschrittenen Methoden/Themen vertraut bin.

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: Unten ist der neue Code, der exponentiell schneller ist. Der Druck der konstanten Linie wurde ebenfalls entfernt, um die Geschwindigkeit noch zu erhöhen.

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

Für den Anfang, wenn bei Teilern suchen, müssen Sie nie weiter als die Quadratwurzel der Anzahl gehen, weil jeder Divisor unter der Quadratwurzel über eine äquivalente hat.

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

Dann müssen Sie die andere Seite der Division zählen:

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

Die Quadratwurzel ist etwas Besonderes, weil es nur einmal zählt, wenn es ganze Zahl ist:

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

Answer 2

Sie haben soeben muss die Nummer faktorisieren. p^a * q^b * r^c hat (a+1)*(b+1)*(c+1) Teiler. Hier finden Sie einige grundlegende Implementierung mit dieser Idee:

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