# Interm. ALg. Scripting - Smallest Common Multiple

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.

P.S.

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

Okay.

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.