Lets, LCM of the numbers $A$ & $B$ is equal to $L$ and their prime factorizations are $-$

$A = p_1^{a_1} . p_2^{a_2} ... p_m^{a_m}$

$B = p_1^{b_1} . p_2^{b_2} ... p_m^{b_m}$

where, $p_1 < p_2 < ... < p_m$

and we know,
$L = p_1^{c_1} . p_2^{c_2} ... p_m^{c_m}$

where, $c_i = max(a_i,b_i)$, where $(1 \leq i \leq m)$

So, we can make $L$ maximum by taking all $a_i = b_i = c_i , (2 \leq i \leq m)$ and for $i = 1$ we will take $a_i = c_i, b_i = c_i-1$ or $a_i = c_i - 1, b_i = c_i$ as $A$ & $B$ are different.

To overcome TLE, iterate through all prime numbers till $10^6$ and it is not more than $78498.$

Contributors

Statistics

48% Solution Ratio
woolgathererEarliest, Feb '21
Kuddus.6068Fastest, 0.0s
steinumLightest, 131 kB
mah20tShortest, 330B
Toph uses cookies. By continuing you agree to our Cookie Policy.