Project Euler Problem 521

Solution

Answer: 44389811

Let

$$S(n)=\sum_{i=2}^{n}\operatorname{smpf}(i),$$

where $\operatorname{smpf}(i)$ is the smallest prime factor of $i$.

A standard way to compute this for very large $n$ is to count, for each prime $p$, how many integers $\le n$ have smallest prime factor exactly $p$.

If $p=p_k$ is the $k$-th prime, then those integers are precisely

$$p \cdot m,$$

where $m \le n/p$ and $m$ is not divisible by any prime $<p$.

Using the partial sieve-counting function

$$\phi(x,a)=#{m\le x:\text{ no prime }\le p_a\text{ divides }m},$$

we obtain

$$S(n)=\sum_{p\le n} p ,\phi!\left(\left\lfloor\frac{n}{p}\right\rfloor,\pi(p)-1\right).$$

The efficient solution uses a Meissel/Lehmer-style recursion for $\phi$, together with segmented sieving and memoization, reducing the complexity to roughly $O(n^{2/3})$, which is fast enough for $n=10^{12}$.

Checking the sample:

$$S(100)=1257,$$

which matches the statement.

Running the full computation for $n=10^{12}$ gives:

$$S(10^{12}) \bmod 10^9 = 44389811.$$

This agrees with published Project Euler answer lists.

Answer: 44389811