# 某島

… : "…アッカリ～ン . .. . " .. .
July 1, 2015

## Project Euler 521. Smallest prime factor

• 小於等於 n 的素數之和。
• 小於等於 n 的合數的最小素因子之和。

```
Int f(LL n){
LL r = sqrt(n); vector<LL> V; REP_1(i, r+1) V.PB(n/i);
int up = int(*V.rbegin()); DWN_1(i, up-1, 1) V.PB(i);

Int z = 0;

unordered_map<LL, LL> dp;

REP(i, V.size()){
LL x = V[i];
dp[x] = x-1;
}

FOR_1(p, 2, r+1) if (dp[p] > dp[p-1]){
LL prev = dp[n];
LL pp = (LL)p*p; for(auto v: V){
if (v < pp) break;
dp[v] -= (dp[v/p] - dp[p-1]);
}
z += Int(p) * Int(prev - dp[n]);
}
return z;
}

Int g(LL n){
LL r = sqrt(n); vector<LL> V; REP_1(i, r+1) V.PB(n/i);
int up = int(*V.rbegin()); DWN_1(i, up-1, 1) V.PB(i);

unordered_map<LL, Int> dp;

REP(i, V.size()){
LL x = V[i];
if (x&1) dp[x] = Int(x) * Int((x+1)/2) - 1;
else dp[x] = Int(x/2) * Int(x+1) - 1;
}

FOR_1(p, 2, r+1) if (dp[p] != dp[p-1]) {
LL pp = (LL)p*p; for(auto v: V){
if (v < pp) break;
dp[v] -= Int(p)*(dp[v/p] - dp[p-1]);
}
}
return dp[n];
}

int main(){

#ifndef ONLINE_JUDGE
freopen("/users/xiaodao/desktop/Exercise/in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif

LL n = 1e12;
cout <<  f(n)  + g(n) << endl;

//44389811
}

```