Project Euler 485 - Maximum Number of Divisors

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

Thought Process

This was quite a straightforward fun problem for me.

My first thought was that if we precompute all the values of d(n), 0 < n < u + 1, then M(n, k) can quite easily be calculated from M(n - 1, k) so we don't have to find the maximum of 100,000 values every time, but instead we just compare the incoming and outgoing values. This problem is commonly known as the Sliding Window Problem.

I found a pretty neat trick using dictionaries. 

Now the problem boils down to being able to quickly calculate d(n), 0 < n < u + 1.

I used a trick which precompute the smallest (or greatest) prime factor sieve. See an implementation of smallest prime factor sieve here: https://www.geeksforgeeks.org/prime-factorization-using-sieve-olog-n-multiple-queries/ 

I was able to solve the problem in ~120 seconds. After some optimization's and using some clever tricks from the thread I got it down to ~85 seconds which I'm very happy with.

Interactive Code

Enter 2 Integers separated by a space (u, k)

Code will output S(u, k)