Analyze the Program

This program has intentionally poorly named variables and no comments. Use your knowledge of C++ to answer to these questions:

a) What is the purpose of the program? / What are the commonalities between the numbers that get printed?

b) Suggest variable names.

c) Can you suggest a better way of acomplishing the same task?

Answer

Here is a version that has comments and descriptive variable names.

#include <iostream>

int main() {

	// Check each number from 0-100000
	for (int dividend = 0; dividend <= 100000; dividend++)
	{
		// This variable tells us if the `dividend` is divisible by all numbers from 1-10.
		bool divisible = true;
		// we start `divisor` at 2 because all integers are divisible by 1
		for (int divisor = 2; divisor <= 10; divisor++)
		{
			if (dividend % divisor != 0)
			{
				// If we find a number that it can't be divided with updates the `divisible` variable and stop searching.
				divisible = false;
				break;
			}
		}

		// If the dividend is divisible by all integers from 1-10 we output it.
		if (divisible)
			std::cout << dividend << ", ";
	}
}

0, 2520, 5040, 7560, 10080, 12600, 15120, 17640, 20160, 22680, 25200, 27720, 30240, 32760, 35280, 37800, 40320, 42840, 45360, 47880, 50400, 52920, 55440, 57960, 60480, 63000, 65520, 68040, 70560, 73080, 75600, 78120, 80640, 83160, 85680, 88200, 90720, 93240, 95760, 98280,

A) The program outputs every integer from 0-100000 that is divisible by every number from 1-10

B) The variable names used in the example above are a little similar, but addequitely descriptive.

C) Many improvements that can be made to this code. Good job if you recognized that being divisible by numbers like 8 and 9 guarantee that a number is divisible by 2, 3, and 4, so there's no reason to include those in the inner loop.

The biggest improvement you can do is change the method all together from a nested loop to using the lowest common multiplier (LCM).

You might have noticed that the output is basically a multiplication table of the number 2520. This is because 2520 is the lowest common multiplier (LCM) for the integers from 1 - 10.

We can find the LCM for a set of numbers by factoring each number into prime components. Then you take the highest power a prime factor is raised to and multiply it with the other highest power prime factors.

Number	Factored	Inclusion Description
1	1^1	does not impact LCM
2	2^1	not highest power of 2
3	3^1	not highest power of 3
4	2^2	not highest power of 2
5	5^1	highest power, will be included
6	3^1*2^1	not highest power of 3 or 2
7	7^1	highest power, will be included
8	2^3	highest power, will be included
9	3^2	highest power, will be included
10	5^1*2^1	5^1 is already included

The final equation then becomes 2^3*3^2*5^1*7^1 = 8*9*5*7 =2520

With this information in mind; here is an improved version that simplifies the matter and improves performance.

#include <iostream>

int main() {
	for (int counter = 0; counter <= 100000; counter+=5*7*8*9) {
		std::cout << counter << ", ";
	}
}

Now the loop runs 39 times (int(100000/2520)) instead of 100000 times.