Project Euler 407 - Idempotents

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

Note: My code runs in ~350 seconds, but my understanding is good so I'm happy with this problem!

Thought Process

Got up to 10^5 with a mad method a year ago, came back to it with renewed knowledge on the Chinese Remainder Theorem and was able to finish it!

This can be solved using the Chinese Remainder Theorem!

From here all I did was find all the divisors of each n, m1 and m2, that are co-prime to each other, because otherwise the CRT is unsolvable, and apply the CRT to all the pairs and returned the maximum.

I also made a sieve to find all divisors initially and then find M(n), this greatly boosted the speed.

My code took about 6mins, but I am very happy with my understanding.

Interactive Code

Enter an integer (yourinput)

Code will output ∑M(n) for 1 ≤ n ≤ yourinput