Time for question number 5 brought to you by Project Euler!

Question 5:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Prime: This one is a bit tricky. Obviously, the brute force method is very simple:

double Run()
{
	int num = 40;

	while(true)
	{
		if(num % 2 == 0 & num % 3 == 0 & num % 4 == 0 & num % 5 == 0 &
			num % 6 == 0 & num % 7 == 0 & num % 8 == 0 & num % 9 == 0 &
			num % 10 == 0 & num % 11 == 0 & num % 12 == 0 & num % 13 == 0 &
			num % 14 == 0 & num % 15 == 0 & num % 16 == 0 & num % 17 == 0 &
			num % 18 == 0 & num % 19 == 0 & num % 20 == 0)
			break;
		else
			num++;
	}

	return num;
}

Results

Limit       Time
20          ~20 minutes
100         unknown
300         unknown

Here I am just looping and checking every number until I find the correct one. Believe you me that this is a very inefficient way to go about it. While it does give me the right answer, it takes about 20 minutes. I don’t even want to check it for more numbers due to the time involvement. You might notice something that I am doing intentionally. I am using the ‘&’ operator (the logical AND). This means that every iteration has 20 modulus checks. There is a very quick and obvious optimization (and the one used almost by default in C++). We will look at that now.

Optimization 1: Once the correct answer is calculated, it becomes easy to see why the above algorithm takes so long to complete. In order to find the correct answer, Prime has to perform 4,655,851,200 modulus comparisons. That can take a while.  We can easily reduce that number by employing something called short-circuit logic. The theory behind short-circuit logic is that if the first test fails, it doesn’t bother with the second test, if the second fails it doesn’t do the third, and so on. Short-circuit logic is performed in C++ with the ‘&&’ operator. I have modified the original code with short circuit logic as can be seen below:

double Run()
{
	int num = 40;

	while(true)
	{
		if(num % 2 == 0 && num % 3 == 0 && num % 4 == 0 && num % 5 == 0 &&
			num % 6 == 0 && num % 7 == 0 && num % 8 == 0 && num % 9 == 0 &&
			num % 10 == 0 && num % 11 == 0 && num % 12 == 0 && num % 13 == 0 &&
			num % 14 == 0 && num % 15 == 0 && num % 16 == 0 && num % 17 == 0 &&
			num % 18 == 0 && num % 19 == 0 && num % 20 == 0)
			break;
		else
			num++;
	}

	return num;
}

Results

Limit       Time
20          714 milliseconds
100         unknown
300         unknown

When this code runs, it completes in 714 milliseconds. That is a huge improvement over prime. Since I don’t know the number of milliseconds prime took, I can compare the number of modulus comparisons required to determine efficiency. I wrote up a quick app that will simulate short-circuit logic with nested if’s and counted the number of tests. This code performed 183,389,427. This means that Prime has to perform 25.3 times as many comparisons as Optimization 1. I intend to benchmark finding numbers evenly divisible by 1-100 and 1-300, but since I don’t want to write that IF statement out, I am waiting for a better solution to do it.

Optimization 2: A minor optimization (the credit of which I owe to my wife) is running the conditional backwards. That is, start at num mod 20 and work my way down to num mod 2. The code for this is simple (just reverse the IF statement). I am not going to list it here for one reason though, it is actually slower (sorry hun). That may seem illogical (it did to me) so I did a little digging. Using my testing code, I determined that starting backwards required my code to run 12,326,489 modulus comparisons to find the right answer. That is actually 14.8 times fewer comparisons than Optimization 1. The problem is that I am doing way more “heavy” comparisons (num mod 20) and much fewer “light” comparisons. The result is that while it may be less work, it takes longer. This did lead me to an interesting thought.

Optimization 3: A thought occurred to me: if a number is divisible by 20, then it is also by default divisible by 10, 5, 4 and 2. Likewise, if it is divisible by 18, then it is also divisible by 9, 6 and 3. I am not going to list the code because…

After running it, Optimization 3 is faster Optimization 2 and still slower than Optimization 1. What we can extrapolate from that is the doing modulus comparisons with the range of numbers 2-10 only equates to about 20 milliseconds of the total 3750+ milliseconds of time. That is only a small fraction. Basically, we need to start small and avoid unneeded “higher number” comparisons at all costs.

Optimization 4: Before I start this one, I want to mention that I am cheating a little bit and hard coding prime values. Since generating prime numbers is outside the domain of this problem (and will be addressed in a later Euler problem) I am ignoring it for now. How you come about having your primes is irrelevant for this problem. For Optimization 4, I am utilizing a method of prime factorization. The basic theory behind this is present in Optimization 3, but like I said before we have to start small and work large to truly be efficient. The idea behind this is that if we can calculate all of the primes smaller than our limit, raised to a power that does not make it larger than our limit, and multiply it all together, we get the smallest number divisible by that range. For instance, if out limit = 2, then our prime is only 2 raised to the 1st power, and 2 is our answer. If our limit = 4, then our primes are 2 and 3 (neither being bigger than 4). The exponent of 2 is 2 (2^2 is not bigger than 4) and our exponent of 3 is 1 (since 3^2 is bigger than 4). We multiply 2^2 * 3 and we get 12 (which is the smallest number divisible by 1, 2, 3, and 4). The same principle applies for this problem. Here our limit = 20, so our numbers are 2^4 * 3^2 * 5 * 7 * 11 * 13 * 17 * 19. Sure we could just plug this in to get the answer (and we’d get the answer in less than 309 nanoseconds), but I want an algorithm that can find the smallest number divisible by all numbers 1 through n. Rewriting the algorithm to incorporate this change, we get:

double primes[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,
     73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,
	 167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,
	 263,269,271,277,281,283,293,307};

double Run()
{
	int limit = 20;
	int primePlace = GetPrimePlace(limit);
	int exponent = 1;
	double total = 1;

	for(int i = 0; i <= primePlace; i++)
	{
		while(pow(primes[i], exponent + 1) < limit)
			exponent++;

		total *= pow(primes[i], exponent);
		exponent = 1;
	}

	return total;
}

int GetPrimePlace(const int upperBound)
{
	int count = 0;
	while(true)
	{
		if(primes[count] >= upperBound)
			return count - 1;
		else
			count++;
	}
}

Results

Limit       Time
20          1 microsecond
100         4 microseconds
300         8 microseconds

As we can see above, our speeds have improved significantly. I can only find 1 speed ratio and that is betweem Optimization 1 and Optimization 4 with a limit of 20. The ratio is 1:714000. A job well done.