Member Avatar for arun_lisieux

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();
}
  • 3 Contributors
  • 5 Replies
  • 518 Views
  • 19 Hours Discussion Span
  • Latest Post Latest Post by arun_lisieux

Dani AI

Generated

Quick diagnosis and a compact fix tied to the replies already here: was right to point toward using the modulo operator for divisibility checks, and was on the money about a control‑flow bug. The inner loop in the original code mutates the candidate while still iterating over divisors, which leaves the divisor counter in an inconsistent state — continue only advances the current loop, it does not restart or escape to the outer loop. Stop testing a candidate as soon as a divisor fails, then move to the next candidate (or, better, avoid the candidate loop entirely with a different algorithm).

A cleaner, faster, and standard approach is to compute the LCM iteratively using the GCD (Euclidean algorithm). Start with result = 1 and for each k from 2 to 20 do result = lcm(result, k), where lcm(a,b) = a / gcd(a,b) * b. That produces the minimal common multiple directly and avoids brute-force searching.

#include <iostream>

using ull = unsigned long long;

ull gcd(ull a, ull b) {
    while (b) { ull t = a % b; a = b; b = t; }
    return a;
}

ull lcm(ull a, ull b) { return a / gcd(a,b) * b; }

int main() {
    ull result = 1;
    for (int i = 2; i <= 20; ++i) result = lcm(result, i);
    std::cout << result << '\n';
}

This is fast and simple; for the 1..20 case the result is 232792560. A couple of practical tips: keep candidate updates in one place (don’t change them inside an inner loop), use break to abandon failing candidates, and use a 64‑bit integer (or big‑integer library) if you generalize to much larger ranges.

Recommended Answers

All 5 Replies

Member Avatar for MosaicFuneral

Have you tried a modulo operation?

Member Avatar for StuXYZ

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.

commented: Excellent, think the problem first, then write code. +27
Member Avatar for StuXYZ

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.

Member Avatar for arun_lisieux

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.

Member Avatar for arun_lisieux

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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.