Project euler exercise 5 approach

Question

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?

So, I tried to do exercise 5 on the project euler, and I came out with this code:

#include <stdio.h> #define TRUE 1 #define FALSE 0 int main () { int n, fnd = FALSE, count, i; for (i = 1; fnd == FALSE; i++) { count = 0; for (n = 1; n <= 20; n++) { count += i % n; } printf ("testing %d, count was: %d\n", i, count); if (count == 0) { fnd = TRUE; printf ("%d\n", i); } } return 0; } 

I believe my apporach is correct, it will surely find a number that is divisible by 1-20. But it was calculated within 5 minutes and still no result. Is my approach right? If so, is there another way to do this? I can not think differently to solve this, the tips will be very much appreciated. Thank you in advance.

EDIT: So, based on the advice I gave you guys, I figured it out, thank you so much! Thus, this is still brute force, but instead of adding 1 to the last number, 2520 is now added, that is, LCM from 1 to 10. And, therefore, calculating if the sum of the residues is a multiple of 2520 is divided by 11 20 was 0. Since 2520 is already divided by 1-10, I needed to divide by 11-20.

 #include <stdio.h> #define TRUE 1 #define FALSE 0 int main () { int n, fnd = FALSE, count, i; for (i = 2520; fnd == FALSE; i = i + 2520) { count = 0; for (n = 11; n <= 20; n++) { count += i % n; } printf ("testing %d, count was: %d\n", i, count); if (count == 0 && i != 0) { fnd = TRUE; printf ("%d\n", i); } } return 0; } 

Thank you so much, I would not have resolved this without your help :) PS: now it calculates in less than 10 seconds.

Answer 1

Your approach is too long because it is a brute force decision. You should be a little smart.

My hint to you is this: what does it mean that a number will be evenly divided by another number? Or is each number below a certain number? Are there common features in simple number factors ? A good starting point should be the Wikipedia page on divisibility .

Answer 2

Hint: you should look for the "least common set."

---

The following hint:

• The answer is the smallest total number (LCM) of numbers 1, 2, 3, ..., 20.
• LCM of n numbers can be found sequentially: if LCM (1, 2) = x, then LCM (1, 2, 3) = LCM (x, 3); if LCM (1, 2, 3) = y than LCM (1, 2, 3, 4) = LCM (y, 4), etc. Therefore, it is enough to know how to find the LCM of any two numbers.
• To find the LCM of two numbers, we can use the following formula: LCM (p, q) = pq / GCD (p, q), where GCD is the largest common factor
• To find a GCD, there is a well-known Euclidean algorithm (perhaps the first non-trivial algorithm on Earth).

Answer 3

I think you should start by calculating the prime coefficients of each number from 2 to 20. Since the desired number should be divisible by each number from 1 to 20, it should also be divisible by each prime coefficient of these numbers.

In addition, it is important to monitor the multiplicities of simple factors. For example, 4 = 2 * 2, so the desired number should be divided by 2 * 2.

Answer 4

Something I quickly baked with Python 3:

 primary_list = [] for i in range(2, 4097): j = i k = 2 delta_list = primary_list[0:] alpha_list = [] while j > 1: if j % k == 0: j /= k alpha_list.append(k) k = 2 else: k += 1 for i in alpha_list: try: delta_list.remove(i) except: primary_list.append(i) final_number = 1 for i in primary_list: final_number *= i print(final_number) 

This is calculated in seconds under a slow machine. Python is very good with abstract numbers. The best tool for the job.

The algorithm is relatively simple. We have a primary list primary_list where we store multiple numbers. Then comes the cycle in which we evaluate the range of numbers that we want to calculate. We use the temporary variable j as a number that can be easily divided, chopped, and subdued. We use k as a divisor, starting at 2 . delta_list is the main working copy of primary_list , where we select the number after the number until only the required " logic " remains. Then we will add these numbers to our main list.

1: 1
2: 2 1
3: 3 1
4: 2 2 1
5: 5 1
6: 2 3 1
7: 7 1
8: 2 2 2 1
9: 3 3 1
10: 2 5 1

The final number is found by multiplying the numbers that we have in primary_list .
1 * 2 * 3 * 2 * 5 * 7 * 2 * 3 = 2520

As said, Python _really _ is good with numbers. This is the best tool for the job. This is why you should use it instead of C, Erlang, Go, D, or any other dynamic / static language for Euler exercises.

Answer 5

I solved this with C. Below is the algorithm!

 #include <stdio.h> #include <stdio.h> int main() { int i; int count; for(i=21;i>0;i++) { count = 0; for( int j=2;j<21;j++) { if (i%j!=0) break; count++; } if (count==19) break; } printf("%d\n",i); return 0; } 

Answer 6

Just some thoughts on the comments above,

@ pg190 you say: "it really only needs to be divided into primes between 1 and 20, that is 2, 3, 5, 7, 11, 13, 17, 19." take 9699690, do not divide by the whole value from 1-20.

So this may be a good solution,

Given a set of numbers [1-20]

The smallest total number can be calculated as follows.

Ex. For numbers 2,6,9

Express them in simple multiplications 2 2

6 2 3

9 3 3

LCM = a multiple of the greatest power of each prime. = 2 * 3 ^ 2 = 18

This can be done taking into account the problem, expressing each number as a simple multiplication and then do this math.

Answer 7

 $num=20; for($j=19;$j>1;$j--) { $num= lcm($j,$num); } echo $num; function lcm($num1, $num2) { $lcm = ($num1*$num2)/(gcd($num1,$num2)); return $lcm; } function gcd($n1,$n2) { $gcd=1; $min=$n1; if($n1>$n2) { $min=$n2; } for($i=$min;$i>1;$i--) { if($n1%$i==0 && $n2%$i==0) { $gcd*=$i; $n1/=$i; $n2/=$i; } } return $gcd; } 

solved in php