Now we can build a sieve backwards from sqrt(N) to 1.

1. Initialise an array a = [0]+[1] * (N+1)

2. Then we start a loop, going through i from sqrt(N) to 1

   • update a[i] = (4) from above, essentially (1) - a[i*j] in the range defined by (3)

3. At the end we have the array a where a[x] = number of integers whose largest square divisor is i*i, clearly we need to go through this list and sum i*i*a[i] and after we sum we mod 1,000,000,007