1.11M Members

Problem to find smallest no divisible by all of the first 20 natural numbers

 
0
 

QUESTION : 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 number that is evenly divisible by all of the numbers from 1 to 20?

While trying to solve this problem, i came up with the code i have given here. The codes compiles and runs, but i get a wrong answer. Someone plz show me where i've gone wrong and help me obtain the correct answer.

#include <iostream>

using namespace std;

class common
{
	public:
		int ans;

		void calc();
};

void common:: calc()
{
	ans = 0;
        int test = 20, flag = 0, i = 1;

	while (flag==0)
	{
		for (i = 1; i<20; i++)
		{
			if (test%i)
			{
				if (i==19)
				{
					ans = test;
					flag = 1;
				}
			}

			else
			{
				test += 20;
				continue;
			}
		}
	}

	cout << "Answer : \t" << ans << endl;
}

int main()
{
	common inst;
	inst.calc();
}
 
0
 

Have you tried a modulo operation?

 
1
 

This is a problem that requires thought NOT code.

The answer can be easily found on a piece of paper.

So without giving you the whole solution try thinking about this
Obviously 20! (20x19x...1) is a solution but it is not the minimum.

Now you have two types of numbers primes and non-primes:
2,3,5,7,11,13,17,19 : so your solution has to be a factor of
2x3x5x7x11x13x17x19 == 9699690
[Sorry I actually did that on calculator ;) ]

Then it is easy, all you have to do is find all the prime factors of each other number and find the lowest common addition to the prime list that you already have. Then you have your answer.

E.g. for the above consider 6: it is 2x3 so no addition is required.
But 4: is 2x2 so you have to add at lease one 2.

That is a much much better way of solving the problem, particularly because if I was setting the problem, next week I would add that I want the lowest 1-1000, and brute force methods will die.

 
0
 

In comment about your ACTUAL code.

The error is that you have a continue .
This is not what you want since it continues the loop. It does not reset i. You can see this error with a simple cout on the start of your for loop.

I am not going to say you need a break . (although it works, the code structure is awful.) Why even test numbers like 1. Surely any integer has this as a factor.

 
0
 

Have you tried a modulo operation?

Ya. The first if loop checks for modulo of i, then the next if loop checks if i=19. If the first if loop is false, then in the else part i have chosen the next multiple of 20 to test. But, If both are true, then i have assumed the value of test as the answer and printed it.

 
0
 

This is a problem that requires thought NOT code.

The answer can be easily found on a piece of paper.

So without giving you the whole solution try thinking about this
Obviously 20! (20x19x...1) is a solution but it is not the minimum.

Now you have two types of numbers primes and non-primes:
2,3,5,7,11,13,17,19 : so your solution has to be a factor of
2x3x5x7x11x13x17x19 == 9699690
[Sorry I actually did that on calculator ;) ]

Then it is easy, all you have to do is find all the prime factors of each other number and find the lowest common addition to the prime list that you already have. Then you have your answer.

E.g. for the above consider 6: it is 2x3 so no addition is required.
But 4: is 2x2 so you have to add at lease one 2.

That is a much much better way of solving the problem, particularly because if I was setting the problem, next week I would add that I want the lowest 1-1000, and brute force methods will die.

Thanks for explaining the logic dude. Am not that bright in math, im currently working on improving that part :) As per the code part, i thought continue statement will stop the current iteration, execute the alteration part of FOR loop, thus altering the value of variable i and move on to the next iteration.

Question Answered as of 5 Years Ago by StuXYZ and MosaicFuneral
You
This question has already been solved: Start a new discussion instead
Post:
Start New Discussion
Tags Related to this Article