Interm. ALg. Scripting - Smallest Common Multiple

The challenges here:

is to calculate the Smallest Common Multiple for a range of integers.

The brute force method is:

  • calculate an array of primes up to SQRT(top-of-range), presumably with Sieve of Eratosthenes - which I just coded in the previous challenge and have now deleted. Arrgh!

  • prime-factor each integer in the range

  • for each prime determine the max-exponent in the prime-factorization over all integers in the range.

  • calculate product over all primes raised to its calculated max-exponent.

Is there a better way? That seems a lot of coding for a mere challenge.


One correction: the primes up to max are required, not just the primes up to sqrt(max) .


No, there is apparently no better way - just bite the bullet and code.

This one only took about 90 minutes once I stopped muttering at it.

Never say never! There is a better algorithm: As I noted originally here:

There is a simpler efficient algorithm that doesn’t require prime factorization of the input range.

  1. Write a Greatest Common Divisor function GCD(a,b) .
  2. Note that the Smallest Common Multiple (SCM) of any two numbers a and b is the value: a * b / GCD(a,b) .
  3. Calculate the SCM for the first two numbers of the range; then successively calculate the SCM for that value plus the next value in the range until you hit the end of the range.

This is far more efficient than a simple integer loop, yet only 1/2 or 1/3 as much code as my earlier prime-factorization algorithm.