Screamed at JavaScript for failing at big integer multiplications. Got it after rewriting in python. Here is my poorly written explanation. --------- MAJOR SPO

Screamed at JavaScript for failing at big integer multiplications. Got it after rewriting in python. Here is my poorly written explanation. --------- MAJOR SPOILERS --------- Let's multiply unique prime numbers and count their factors. n Number of factors 2 2 (1, 2) 2x3 4 (1, 2, 3, 6) 2x3x5 8 2x3x5x7 16 Notice that each time you add a new prime number, the factor count doubles i.e. 2x3x5x...x500500th prime will have 2^500500 factors The 500500th prime is 7376507 (thanks to wolframalpha), and it's not very big. We can easily get the product of the above with 500500 multiplications while modding result of each step by 500500507 to get an answer. Except that the product of first 500500 primes isn't the smallest number containing 2^500500 factors. This can be made smaller. Observe that (2x3x5x...x500499th prime)x2 has 2^500499 + 2^500498 factors. This is because with the extra 2 we added, it produces additional factors with existing factors that are a multiples of 2. Continuing with this, we see that (2x3x5x...x500499th prime) x (2 x 2) has 2^500499 + 2^500498 + 2^500498 = 2^500500 factors. This is a better solution, since 2x2 is smaller than the 500500th prime. If we want continue doubling factor count by multiplying 2s, we will need to multiply by 2x2x2x2 next, and 2^8 after, which becomes inefficient quickly. Instead, why not use 3? Multiplying (2x3x5x...x500499th prime) by (3 x 3) also doubles the factor count. So at this point, we think about doubling factor count and the ways we can do it. Out options are <1>. Multiply by a prime that we have never used so far <2>. Multiply by an existing prime k + 1 times, where k is the number of times it has been used We repeat this 500500 times, using rule <1> and <2> (which can be generalized to one rule) and the result is the final answer. factor count n 2 2 4 2*3 <1> 8 2*3*2*2 <2> 16 2*3*2*2*5 <1> 32 2*3*2*2*5*7 <1> 64 2*3*2*2*5*7*3*3 <2> 128 2*3*2*2*5*7*3*3*11 <1> For 16 factors the number works out to be 120 (just like the example!). For numbers shown in the questions, sieving the prime takes some time, I also found it helpful to use a binary heap for speeding up finding the next smallest factors.