Euler Project 5

Question

2520 is the smallest number that can be divided into each of the numbers from 1 to 10 without a remainder.

What is the smallest positive number evenly divided by all numbers from 1 to 20?

My decision:

#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=mn; else n=nm; } return m; } int lcm(int a, int b) { return ((a*b)/gcd(a, b)); } 

Tell me, where am I mistaken? It shows only a blank screen at startup.

Answer 1

If you have only one lesson to learn from this exercise, do this: the order in which your multiplications and divisions are done. .

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

(PS, of course, you also need to fix a mistake in your logic: you should not multiply x by lcm).

EDIT

To understand why order matters here, consider computing lcm 232792560 and 20 . 232792560 is divided by 20 , so this is the value of lcm . However, when you calculate 232792560*20 , you get an overflow; then you divide by 20 , but you don’t get 232792560 back.

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

Answer 2

Most of the problems in Project Euler can be solved in three ways:

• with brute force
• with an algorithm that solves a more general problem (like you)
• with an intelligent solution requiring no more than pencil and paper

If you are interested in a good solution, rather than fixing a code, try concentrating on the latter approach:

The trick is to find the smallest multiset of primes, so that any number from 1 to 20 can be expressed as the 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 

Under "ORing", the main coefficients of numbers from 1 to 10 get 1*2*2*2*3*3*5*7 , which, as expected, is 2520.

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 really accepted by Project Euler.

Answer 3

A printf() will show you that the code is in an infinite loop. I added printf() to gcd() in a while .

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

while(m!=n) never executed for n=14 . Finally, m and n overflow because x goes over to a larger number that cannot be used by int !

Answer 4

Error 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

n-1 must be n; and x = lcm (...) not x * = lcm (...). But I do not quite understand (from the terminal) where your loop is looping.

Answer 6

Reply on 20: 232792560.

These are all answers for all numbers, the answers to which answer with 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 the Euler question P5 for dividing by 1-10 without a 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 a 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 7

There is no need to write a program for this. My decision:

Write down all primes that do not exceed the largest divisible number.

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

Then, if any of the square root of the primes is not greater than the largest divisible number (in our example - 20), you replace the original prime 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 the new line numbers:
16, 3, 5, 7, 11, 13, 17, 19.

The same goes for 3: 3 * 3> 20, but 3 * 3 * 3 <20. 3 * 3 = 9, so the new number line: 16, 9, 5, 7, 11, 13, 17, 19. 5 * 5> 20, so this is the last line.

Multiply all the numbers in the line and you get the answer: 16 * 9 * 5 * 7 * 11 * 13 * 17 * 19 = 232 792 560