Project Euler 5

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

My solution:

#include<stdio.h>
int gcd(int m, int n);
int lcm(int a, int b);
int main()
{
    int x=1, i;
    for(i=1; i<20; i++)
    {
        x=lcm(x, i+1);
    }
    printf("The answer is:\t%d", x);
    return 0;
}

int gcd(int m, int n)
{
    while(m!=n)
    {
        if(m>n)
        m=m-n;
        else
        n=n-m;
    }
    return m;
}

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

Please tell where I am wrong? It shows only blank screen on running.

Answer 1

There is no need to write a program at all for this one. My solution:

Write down all prime numbers that are not greater than the highest divisible number.

For 20 its: 2, 3, 5, 7, 11, 13, 17, 19.

Then if any of the prime numbers square root is not greater than the highest divisible number(20 in this example), you replace the original prime number with its square root.

In this example 2*2 > 20, 2*2*2 > 20, 2*2*2*2 > 20, but 2*2*2*2*2 < 20. 2*2*2*2 = 16 so new number lines is:
16, 3, 5, 7, 11, 13, 17, 19.

Same for 3: 3*3 > 20 but 3*3*3 < 20. 3*3 = 9, so new number line: 16, 9, 5, 7, 11, 13, 17, 19. 5*5 > 20, so this is final line.

Multiple all numbers int the line and you get answer: 16 * 9 * 5 * 7 * 11 * 13 * 17 * 19 = 232,792,560‬

Answer 2

Most problems on Project Euler can be solved in three ways:

• with brute-force
• with an algorithm that solves a more general problem (like you do)
• with a smart solution that requires pencil and paper at most

If you're interested in a nice solution rather than fixing your code, try concentrating on the last approach:

The trick is to find the smallest multiset of primes such that any number between 1 and 20 can be expressed as a product of some of these primes.

1 = 1      11 = 11
2 = 2      12 = 2*2*3
3 = 3      13 = 13
4 = 2*2    14 = 2*7
5 = 5      15 = 3*5
6 = 2*3    16 = 2*2*2*2
7 = 7      17 = 17
8 = 2*2*2  18 = 2*3*3
9 = 3*3    19 = 19
10 = 2*5   20 = 2*2*5

By "ORing" the prime factors for the numbers between 1 and 10, we get 1*2*2*2*3*3*5*7, which happens to be 2520, just as expected.

Now if we go from 1 to 20, we get 1*2*2*2*2*3*3*5*7*11*13*17*19, which is indeed accepted by Project Euler.

Answer 3

The answer for 20 is: 232792560.

These are all answers for all numbers of which the answer fits in a long integer:

1 : 1
2 : 2
3 : 6
4 : 12
5 : 60
6 : 60
7 : 420
8 : 840
9 : 2520
10 : 2520 <=== example in Euler P5 question for division by 1 to 10 without remainder
11 : 27720
12 : 27720
13 : 360360
14 : 360360
15 : 360360
16 : 720720
17 : 12252240
18 : 12252240
19 : 232792560
20 : 232792560 <== answer for Euler Prog 5 (1 to 20 without remainder
21 : 232792560
22 : 232792560
23 : 5354228880
24 : 5354228880
25 : 26771144400
26 : 26771144400
27 : 80313433200
28 : 80313433200
29 : 2329089562800
30 : 2329089562800
31 : 72201776446800
32 : 144403552893600
33 : 144403552893600
34 : 144403552893600
35 : 144403552893600
36 : 144403552893600
37 : 5342931457063200
38 : 5342931457063200
39 : 5342931457063200
40 : 5342931457063200
41 : 219060189739591200
42 : 219060189739591200

Answer 4

The bug is x*=lcm(x, i+1); and here is the complete solution,

long gcd(long m, long n);
long lcm(long a, long b);

int main()
{
    long x=1;
    for(int i=2; i<=20; i++)
    {
        x=lcm(x,i);
    }
    cout << "The answer is: " << x << endl;
    return 0;
}

long gcd(long a, long b)
{
        return (b==0)?a:gcd(b,a%b);
}

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

Answer 5

A printf() would show you that you're code is getting into an infinite loop. I've added a printf() in the gcd() in the while loop.

    n=n-m;
    printf("m=%d n=%d\n", m, n); 
}   
return m;

while(m!=n) is never true for n=14. Finally the m and n overflows because x goes to a higher number which cannot be accommodated by int type!

Answer 6

If there should be only one lesson that you learn from this exercise, make it this: the order in which you do your multiplications and divisions matters.

Even if it does not matter in mathematics, it often matters in your program. For example, in math there is no difference between (a*b)/gcd(a, b) and a/gcd(a, b)*b; In your program, it would make the difference between passing and failing.

(P.S. of course you need to fix the bug in your logic, too: you should not be multiplying x by lcm).

EDIT

To understand why the order makes the difference here, consider calculating lcm of 232792560 and 20. 232792560 is divisible by 20, so it is the lcm. However, when you calculate 232792560*20, you get an overflow; then you divide by 20, but you do not get 232792560 back.

Since the divisor is gcd(a,b), you can divide it out of a before multiplying by b without truncating the result by integer division. This little trick that experienced programmers use without thinking can save you hours of debugging.

Answer 7

The n-1 should be n; and x =lcm(...) not x*=lcm(...). But I don't quite see (away from terminal) where your loop gets stuck.