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.
- Write a Greatest Common Divisor function
- Note that the Smallest Common Multiple (SCM) of any two numbers a and b is the value:
a * b / GCD(a,b) .
- 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.