2
$\begingroup$

Suppose I want to find a number that is divisible by all 3 digit numbers (100-999), how do I write a code for that. I know only "1" can divide all 3 digit numbers, but I just want to know the logic.

$\endgroup$
2
  • $\begingroup$ 7128865274665093053166384155714272920668358861885893040452001991154324087581111499476444151913871586911717817019575256512980264067621009251465871004305131072686268143200196609974862745937188343705015434452523739745298963145674982128236956232823794011068809262317708861979540791247754558049326475737829923352751796735248042463638051137034331214781746850878453485678021888075373249921995672056932029099390891687487672697950931603520000 $\endgroup$ Nov 4, 2020 at 16:40
  • $\begingroup$ Python-specific questions are off-topic here, so I removed "python" from the title. $\endgroup$ Nov 4, 2020 at 16:41

1 Answer 1

3
$\begingroup$

The number you see is known as the least common multiple.

$\endgroup$
8
  • 1
    $\begingroup$ Another solution is to use a prime sieve, and then to calculate for each prime its highest power appearing in the given range. This should work if the range starts at 1, and might be adaptable to the general case. $\endgroup$ Nov 4, 2020 at 16:38
  • 1
    $\begingroup$ @YuvalFilmus I think just computing the LCM iteratively is a better idea. It's more flexible (regarding inputs) and scales within polylog(n) terms asymptotically for the [1, n] case compared to the sieve (can't be bothered figuring out which one ends up slightly faster). $\endgroup$
    – orlp
    Nov 4, 2020 at 17:57
  • 1
    $\begingroup$ @orlp Not for an interval of numbers. The thing is that one can tell which is going to be the largest exponent of any given prime appearing in any of the numbers in the interval just from the end-points, by doing a binary search, for example. The rest is just to compute all the primes less than or equal to the larger end-point and get their exponents. Them multiply all those primes raised to their exponents. $\endgroup$
    – plop
    Nov 4, 2020 at 18:04
  • $\begingroup$ @orlp what if I want to find multiple numbers divisible by all numbers in a given range. LCM won't be able to do that. It would only generate 1 number divisible by all the numbers in the given range. $\endgroup$ Nov 4, 2020 at 18:09
  • $\begingroup$ @orlp Let me define exponent in case other people use other names. The exponent of a prime $p$ in an integer $a$ is the largest $n\in\mathbb{N}$ such that $p^n$ divides $a$. $\endgroup$
    – plop
    Nov 4, 2020 at 18:11

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.