Before we get to the slowness aspect of this code, there are a few other things we should straighten out first:
In order to better understand your code, it is helpful to have better variable names.
Whenever you see yourself adding a comment after each variable name to describe it, you are doing something wrong:
int f = 0; //divisors
int m = 500; //max divisors
int j = 1; //current number
int z = 0; //sum (last run achieved: 135878572)
int a = 1; //current denominator
String t = ""; //total divisors
Not to mention that this is just confusing:
System.out.println("t: " + z);
System.out.println("f: " + t);
System.out.println("d: " + f);
System.out.print("Answer: " + z);
I would have expected something like:
System.out.println("t: " + t);
System.out.println("f: " + f);
System.out.println("d: " + d);
But your output is not very informative at all about what it actually means.
Now, how about we do this?
int divisors = 0;
int maxDivisors = 500;
int currentNumber = 1;
int sum = 0;
int currentDenominator = 1;
String totalDivisors = "";
Now there's no longer a need for the comments describing each variable, and now it will be easier to understand your code.
String concatenation and System.out
A major bottleneck in your code is all the
System.out.println messages. You can take the fastest code in the world, and add a bunch of calls to
System.out.println to it and it will become a lot slower.
Additionally, actually storing and outputting all the divisors is a major bottleneck. You are storing the divisors by using String concatenation. String concatenation by using the
+= operator is slow, as a new String object is created every time. It is slightly faster to use the
StringBuilder class to perform string concatenation. However, in this case I would recommend getting rid of this output entirely. Once you have checked that the calculation of the number of divisors is correct, you don't need to know what the exact divisors are anymore.
Now to the fun part. Your way of calculating the number of divisors is the good old brute-force-ish way. Loop from 1 to x and see if it is divisible. Makes sense.
But there is a much much much faster way.
Let's take a look at some numbers, shall we?
Let's take a look at the prime factorization for those numbers
Number Divisors Prime Factorization
6 4 2*3
28 6 2*2*7
36 9 2*2*3*3
66 8 2*3*11
120 16 2*2*2*3*5
In how many different ways can we pick the prime factorizations for each of these numbers?
Let's take a look at 36. There are 2x
2's in the prime factorization and 2x
3's. So we can pick 0-2
2's (three combinations) and 0-2
3's (three combinations). 3 combinations * 3 combinations = 9 !!
Coincidence? Let's take a look at 120. There are three 2's, one 3, and one 5. So there's four combinations to pick 2's, two combinations to pick 3's and two combinations to pick 5's. 4*2*2 = 16.
Coincidence? Absolutely not.
Note that we don't actually need to do the actual prime factorization, we just need to know in how many different ways we can pick the prime factors.
Assume that the prime factorization is
x*x*x*y*y*z, then there will be 4*3*2 = 24 divisors for that number. No matter what the values of x, y and z are.
This is just a push in the right direction, now I will leave the fun part of implementing the code up to you (or, if you really really just want the codes, which I don't recommend, you can take a look at one of my previous questions in which I have implemented this fast approach)