Project Euler 675 - 2^ω(n)

Official link: https://projecteuler.net/problem=675

Note: My code runs in ~130 seconds (brought down to 55s with pypy), but my sieve is quick and my understanding is good so I'm happy with this problem!

Thought Process

Using a bit of research we can find some highly helpful identities (https://en.wikipedia.org/wiki/Prime_omega_function), this immediately gives us a simplification for S(n)

Now with a sieve that finds all the prime factors and their corresponding exponents, we can continuously calculate F(n) by updating a running total, and storing the current exponents in a dictionary (or whichever data structure you prefer).

Also because our answer is mod 1,000,000,087 we can use modular division to greatly speed up the division process

Interactive Code

Input an integer (yourinput)

Code will output F(yourinput) mod 1000000087