NC53079 Forsaken喜欢数论(数论)

题目链接

题意：

题解：

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N = 3e7 + 10; 
int prime[N];     
int miniFactor[N];
int primepos;
void init() {
    int tmp;
    for (int i = 2; i < N; i++) {
        if (!miniFactor[i]) prime[primepos++] = i, miniFactor[i] = i;
        for (int j = 0; (tmp = i * prime[j]) < N; j++) 
        {
            miniFactor[tmp] = prime[j];
            if (!(i % prime[j])) break;
        }
    }
}
int main() 
{
    init();
    int n;
    long long sum;
    cin>>n;
    for(int i=1;i<=n;i++)
    sum+=miniFactor[i];
    cout<<sum<<endl;
    return 0;
}