How to speed up this program?

Question

I am currently trying to solve a ProjectEuler problem and I have everything except speed. I am pretty sure that the program runs so slowly due to nested loops. I would like some tips on how to speed this up. I am a beginner programmer, so I am not familiar with many more complex methods / topics.

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: Below is the new code, which is exponentially faster. Permanent printing has also been removed to speed it up.

 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

To begin with, when you look at the divisors, you no longer need to go beyond the root square of the number, because each divisor under the square root has the equivalent above.

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

Then you need to calculate the other side of the division:

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

The square root is special because it counts only once if it is an integer:

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

Answer 2

You just need to expand the number. p^a * q^b * r^c has (a+1)*(b+1)*(c+1) divisors. Here are some basic implementations using this idea:

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