if (num % multiple != 0) {
isMultiple = false;
}
I got a five times speed improvement simply by adding a break; to this.
if (num % multiple != 0) {
isMultiple = false;
break;
}
Now it doesn't keep checking 4, etc. after failing on 3.
for(int num = 2; num < 1000000000; num += 2) {
Why 2? If you're going with this kind of speedup, go ahead and use what you know.
for (int num = 2520; num < 1000000000; num += 2520) {
And if you do that, change
for (int multiple = 1; multiple <= 20; multiple++) {
to
for (int factorCandidate = 11; factorCandidate <= 20; factorCandidate++) {
I changed the incorrect multiple to factorCandidate because I found multiple confusing. It wasn't a multiple of anything. It was a candidate to be one of the factors of the number. Another alternative would be to simply call it i, which at least is not misleading about what it does (if a bit uninformative).
This works because you already know that it's divisible by the first ten (your original could have started at 3 for the same reason, since all numbers are divisible by 1 and you only checked even numbers).
If we start at 2520 and increment only by multiples of 2520, then we maintain the property that it is divisible by all of the first ten numbers. If we would instead add one, then we would lose that property. The most obvious example is that we would no longer be divisible by 2, as the even number would become odd. But in fact, we wouldn't be divisible by any of the first ten numbers except 1. Similarly, 27,720 (11*2520) is the least common multiple of 1 to 11. All greater multiples are multiples of it.
The combination of those two changes speeds up the algorithm by almost a thousand times.
But that suggests a new algorithm. Rather than iterating to find the Least Common Multiple (LCM) of 1 to 20 directly, why not find the LCM of 1 to 11 and use that to get the LCM of 1 to 12, etc.?
int smallest = 0;
for(int num = 2; num < 1000000000; num += 2) {
boolean isMultiple = true;
for (int multiple = 1; multiple <= 20; multiple++) {
if (num % multiple != 0) {
isMultiple = false;
}
}
if (isMultiple == true) {
smallest = num;
break;
}
}
So replace all of this with
int smallest = 2520;
for (int nextFactor = 11; nextFactor <= 20; nextFactor++) {
for (int previous = smallest; smallest % nextFactor != 0; smallest += previous) ;
}
That gives another hundred times speedup. This solution is actually faster than the mathematical solution using the greatest common divisor (GCD) to determine the LCM. At least for the range 1 to 20.
int smallest = 2520;
for (int nextFactor = 11; nextFactor <= n; nextFactor++) {
smallest *= nextFactor / gcd(nextFactor, smallest);
}
Note that this works by the same principles that justified incrementing by 2520 earlier.
Of course, the fastest runtime solution is just
int smallest = 16 * 9 * 5 * 7 * 11 * 13 * 17 * 19;
The compiler will go ahead and calculate that for you. That's just the largest multiple of each prime that appears in the range 1 to 20. Note that only 2 and 3 get higher multiples than just themselves. This is because 5 * 5 is greater than 20 as are all integer powers of larger primes.
You can implement this more generally with a sieve.
int [] divisors = new int[20];
for (int i = 0; i < divisors.length; i++) {
divisors[i] = i + 1;
}
for (int i = 1; i < divisors.length; i++) {
for (int j = i + 1; j < divisors.length; j++) {
if (divisors[j] % divisors[i] == 0) {
divisors[j] /= divisors[i];
}
}
}
int smallest = divisors[0];
for (int i = 1; i < divisors.length; i++) {
smallest *= divisors[i];
}
But of course, it isn't as fast that way. We can write out the same result manually:
int smallest = 1 * 2 * 3 * 2 * 5 * 1 * 7 * 2 * 3 * 1;
smallest *= 11 * 1 * 13 * 1 * 1 * 2 * 17 * 1 * 19 * 1;
But I find it easier to read without the ones and with like divisors grouped (as 16, 9, etc.).
Using the sieve this way allows us to avoid explicitly calculating which numbers are prime, which are powers, and which are composites with multiple prime factors (the ones). We sieve out extra factors directly.
The sieve is relatively fast, but not as much so as the GCD solution or the simple increment by the previous LCM solution.
