UVA 10680 - LCM

http://uva.onlinejudge.org/external/106/10680.html

This problem ask you to calculate the last non-zero digit of the $LCM(1...n)$, where $n$ is between 1 <= n <= 10^6.

The LCM of two integers $a$ and $b$  is the smallest positive integer that is a multiple of both $a$ and $b$.

$$\operatorname{lcm}(a,b)=\frac{|a\cdot b|}{\operatorname{gcd}(a,b)}$$

Another way to define the LCM between two integers $a$ and $b$ is from their respective standard prime factorization. For each prime factor of $a$ and $b$ we take the maximum exponent.

$$\operatorname{lcm}(a,b) = \prod_p p^{\max(a_p, b_p)}$$

I solved this problem using the second definition of LCM. The idea is simple if we want to calculate the LCM for the numbers of $1, 2, 3, \cdots, n$ we first list all the prime factors between $[1, n]$. For each factor in that list we need the maximum exponent such that $p^{x} \leq n$. In other words, let's say that $n = 20$ we want to know the highest power of 2 in the $LCM(1, 2, \cdots, 20)$ we can try the following:

$2^{1} \leq 20$ (true)

$2^{2} \leq 20$ (true)

$2^{3} \leq 20$ (true)

$2^{4} \leq 20$ (true)

$2^{5} \leq 20$ (false)

So the largest power of 2 in the $LCM(1, 2, \cdots, 20)$ is $2^{4}$.

 

We repeat this process for the other prime factor in the range $[1,n]$. After that for each prime factor we calculate the answer mod 10. To avoid getting 0's at the end we subtract the $cnt2 - cnt5$, because between $1, 2, 3, \cdots, n$ always there is going to be more factors of two than factors of five, this subtraction is always going to be greater than 0. In addition, To speed-up the algorithm the prime factors are pre-calculated using Sieve of Eratosthenes.