jzbakos jzbakos - 1 month ago 13
Java Question

How would I speed up this program?

I am currently attempting to solve a ProjectEuler problem and I have got everything down, except the speed. I am almost certain the reason the program executes so slowly is due to the nested loops. I would love some advice on how to speed this up. I am a novice programmer, so I am not familiar with a lot of the more advanced 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.");
}
}
}

Answer

For starters, when looking at divisors, you never need to go further than the root square of the number, because each divisor below the square root has an equivalent above.

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

Then you need to count 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 integer. Fortunately, triangle numbers are not square, so you don't have to worry about it.

Comments