CODEWITHSUNDEEP
c++
malxmusician212
malxmusician212

Reputation: 113

Project Euler #5

I have a question concerning Project Euler Task 5, in C++, which is: 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?

I have written code, that I think should work, but it doesn't...I honestly have no idea why it doesn't, so any help would be really appreciated:

#include <iostream>

using namespace std;

int main()
{
  int smallestprod = 1;

  for (int ii = 1; ii <= 20; ii++)
    {
      if (smallestprod % ii != 0)
        smallestprod *= ii;
    }

  cout << "The integer you are looking for is: " << smallestprod << "\n";
  system("pause");
}

I've tried checking my work by placing the loop:

for (int jj = 1; jj <= 20; jj++)
  {
    cout << smallestprod % jj << "\n";
  }

I would hope that the output would be all 0s (for the jj section of the loop), due to the logic in my ii for loop, but I get some nonzero numbers, which results in my getting the incorrect answer... I have been fooling around with this for a while, and really don't see where the logic in the ii for loop screws up...help please?

Upvotes: 0

Views: 1703

Answers (4)

singhiskng
singhiskng

Reputation: 511

i think you should try this.
this is just a pseudocode

var n=1
while(1){
    if (n%1==0 && n%2==0 && .....n%20==0){
        print n
        break
    }
    n++
}

it will give your answer as fast as you can think

Upvotes: 0

tkhomas
tkhomas

Reputation: 123

When you multiply all the numbers from 1 to 20 you will get an overflow for the standard 32-bit int, which maximum value is only 2 147 483 647. So, it's impossible to store such a multiplication result in the int variable and that's the reason for "strange" effects you have discovered in the output.

But you don't really need to multiply all the numbers from 1 to 20 to get the answer. Finding out all the prime factors that appear in given range and their multiplicity will be enough to solve the problem.

Upvotes: 0

Oleg Mikheev
Oleg Mikheev

Reputation: 17444

I would break your code into multiple methods, each solving it's own problem. As it's already mentioned the greatest common divisor is the basis for calculation of least common multiple, so

int greatestCommonDivisor(int a, int b)
{
}

LCM of two numbers is

int greatestCommonDivisor(int a, int b)
{
}

And LCM of array of numbers seems to be solved by just calling greatestCommonDivisor(int a, int b) in a loop:

int leastCommonMultiple(int[] nums, int len)
{
    int curr = 1;
    for(int i = len-1; i >= 0; --i) {
        curr = leastCommonMultiple(curr, nums[i]);
    }
    return curr;
}

Upvotes: 0

James King
James King

Reputation: 6365

I think you're getting a number that will be too big, and also it is confusing to call a variable which is not usually prime "smallest prime".

Trace through the loop by hand:

i=1; smallestprime = 1
i=2; smallestprime = 1 * 2
i=3; smallestprime = 2 * 3
i=4; smallestprime = 6 * 4

But in the last step you only needed to multiply by 2 in order to ensure your answer was divisible by 4. (12 is the smallest number divisible 1, 2, 3, 4, not 24).

I think it you try a few examples by hand, such as manually calculating the 2520 number, it will become clearer what to do. Basically as you loop through integers k accumulating the answer N, you need to multiply by some subset of the prime factors of k - just enough to make N divisible by k, but no more.

Probably the most efficient way to do this is to use the relationship between LCM and GCD, and calculate the LCM using the Euclidean algorithm.

Upvotes: 2

Related Questions