0%

Problem 521


Problem 521


Smallest prime factor

Let smpf(n) be the smallest prime factor of n.
smpf(91)=7 because 91=7×13 and smpf(45)=3 because 45=3×3×5.
Let S(n) be the sum of smpf(i) for 2 ≤ i ≤ n.
E.g. S(100)=1257.

Find S(1012) mod 109.


最小质因数

记smpf(n)为n的最小质因数。
例如,smpf(91)=7,因为91=7×13;smpf(45)=3,因为45=3×3×5。
对于所有2 ≤ i ≤ n,记S(n)为smpf(i)的和。
例如,S(100)=1257。

求S(1012) mod 109