2
$\begingroup$

I'm trying to learn computer science by doing some challenges. One is the following.

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?

Let's generalize the problem from $1$ to $n$.

I thought of a loop between $n$ and $n/2$ as everything above $n/2$ is a multiple of something between $1$ and $n/2$. At each iteration, the result is the least common multiple of the loop variable and the precedent result (at the beginning the result is 1).

If I am correct, the complexity of this should be $\mathcal{O}(n/2)$. Am I right?

Is there any more efficient algorithms to solve this problem? If so witch one and what is their complexity?

$\endgroup$
3
  • $\begingroup$ You will indeed have $O(n/2)$ loop iterations, however at each one, you need to find the GCD of two numbers, which is not constant time and thus your overall runtime will be be greater than $O(n/2)$ How are you calculating GCD? $\endgroup$ Commented Apr 20, 2019 at 14:11
  • $\begingroup$ @BryceKille I'm using Euclid's algorithm with modulo. $\endgroup$
    – o2640110
    Commented Apr 20, 2019 at 15:23
  • $\begingroup$ Ok. So at every step $i$, you are computing $GCD(i, prec)$ where $prec$ is the precedent result, which is certainly greater than $i$. Therefore at every step, you have $O(\log i)$ complexity. Even if you only do half of the loops, this will still end up being $O(n\log n)$ then. $\endgroup$ Commented Apr 20, 2019 at 15:45

2 Answers 2

1
$\begingroup$

Suppose that we are interested in the LCM of all numbers from $1$ to $n$. It is not hard to check that the answer is the product of $p^{k_p}$ for all primes $p \leq n$, where $k_p$ is the largest integer such that $p^{k_p} \leq n$. For example, the primes at most 10 are $2,3,5,7$, and so the answer is $$ 2^3 \cdot 3^2 \cdot 5 \cdot 7 = 2520. $$ Similarly, the primes at most 20 are $2,3,5,7,11,13,17,19$, and so the answer is $$ 2^4 \cdot 3^2 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19. $$

$\endgroup$
3
  • $\begingroup$ Is there any algorithm that can calculate this in en efficient way? $\endgroup$
    – o2640110
    Commented Apr 20, 2019 at 15:28
  • $\begingroup$ Sieve of Eratosthenes. $\endgroup$ Commented Apr 20, 2019 at 15:45
  • $\begingroup$ Note that the output will be quite large, $\Theta(n)$ bits. $\endgroup$ Commented Apr 20, 2019 at 15:48
0
$\begingroup$

[Answer to the complexity part] The complexity is surely greater than O(n/2) because finding least common multiple also carries some non-constant complexity. Check out GCD by Euclidean algorithm. If you are calculating GCD of a and b, the complexity would be O(log(min(a,b)). Also, complexity of calculating GCD(a,b) and LCM(a,b) are same because one of them can be calculated in constant time if the other is known.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.