I'm working on a problem for a programming challenge (obfuscated to make googling this thread harder: it's # 22

^{2}in rot13(Cebwrpg Rhyre)). It devolves to computing the sum of a multiplicative function f(n) over a large interval (1 < n ≤ M). According to threads in other forums, this can be done via inclusion-exclusion in O(√M) time, using the primes < √M as the basis set for inclusion-exclusion. However, there's 4,157,407 in that basis, so in my (limited) understanding of inclusion-exclusion, there would be 2

^{4157407}terms to wrangle, which is clearly way too many. So there's got to be a way to exclude large swaths of the inclusion-exclusion terms, but I don't see a good way to do this.

If it helps, the function f(n) is 1 whenever n is squarefree, and on prime powers, we have f(p

^{e}) = p

^{e}if p divides e and f(p

^{e}) = p

^{e-1}otherwise.

Can anyone help?