Project Euler: Problem 12

Problem 12

Approach

Prime factorization was used in problem 3 - we'll use the same idea here.

We'll repeatedly divide the triangle number first by 2, then by 3, 5, 7, etc.

This results in some unnecessary checks because we'll try non-prime numbers like 9, 15, etc. A way around this is to generate the primes up front and save them (e.g., via the Sieve of Eratosthenes). But we aren't dealing with extremely large numbers here so I've chosen to skip that step.

A map() object is used to store key:value pairs of factor:count. This also isn't necessary but it made debugging a bit easier.

It is known that any number, $X$, can be represented by it's prime factors via:
$X = f_1^{c_1} \cdot f_2^{c_2} \cdot ... \cdot f_n^{c_n}$
where $f$ is a prime factor and $c$ is the exponent.

Examples:

• $10 = 2^{1} \cdot 5^{1}$
• $36 = 2^{2} \cdot 3^{2}$

It is also known that the total number of factors of a number can be calculated taking the product of each exponent+1 of each prime factor.

Examples:

• There are 4 factors of 10: (1, 2, 5, 10). Or, $(1 + 1) \cdot (1 + 1) = 4$
• There are 9 factors of 36: (1, 2, 3, 4, 6, 9, 12, 18, 36). Or, $(2 + 1) \cdot (2 + 1) = 9$

JS Solution

Conclusion

Final answer

$76576500$