Project Euler 745 - Sum of Squares

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

Thought Process

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

Interactive Code

Enter a number (yourinput)

Code will output S(yourinput) % 1,000,000,007