题解 | #Forsaken喜欢数论#

• 欧拉筛
• 题解

欧拉筛

欧拉筛法可以在线性的时间复杂度里筛出N以内的所有质数

vector<long long> oula(long long n)
{
    vector<long long> prime;
    vector<bool> vis(n + 1);
    for (int i = 2; i <= n; i++)
    {
        if (!vis[i])
            prime.emplace_back(i);
        for (int j = 0; j < prime.size(); j++)
        {
            if (prime[j] * i > n)
                break;
            vis[prime[j] * i] = true;
            if (i % prime[j] == 0)
                break;
        }
    }
    return prime;
}

设$a=p\ast ba=p*b$,其中p是a的最小质因子，那么b<a。对于外层循环来讲，b一定先被遍历到，我们可以推出b的最小质因子一定大于等于p，所以p一定先被筛掉。假设当外层循环遍历到b时，内存循环一定可以在此时同时筛掉b和a。而且在没有遍历到b时，b也有可能已经被筛掉了。令a为全体合数，那么就能保证所有合数都被筛掉。

题解

本题就是在求前n个数字的最小质因子。我们使用欧拉筛，在每个数被筛掉时候，标记即可。再通过遍历相加得到答案。对于偶数的答案可以使用$\lfloor n\mathrm{/}2\rfloor \ast 2\backslash lfloor\; n/2\backslash rfloor*2$

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using ull = unsigned long long int;
using pll = pair<ll, ll>;
const ll mod = 1e9 + 7;
const int N = 3e7 + 250;
//用数组标记，禁止用哈希表，会出现TLE
long long mp[N];
void Euler(long long int n)
{
    vector<long long> prime;
    vector<long long> vis(n + 1);
    for (long long int i = 2; i <= n; i++)
    {
        if (!vis[i])
        {
            prime.emplace_back(i);
            //质数的最小质因子就是其本身
            mp[i] = i;
        }
        for (int j = 0; j < prime.size(); j++)
        {
            if (prime[j] * i >= n)
                break;
            //prime[j]*i这个数的最小质因子为prime[j]和i的最小值
            mp[prime[j] * i] = min(prime[j], i);
            vis[prime[j] * i] = true;
            if (i % prime[j] == 0)
                break;
        }
    }
}
void dilingtian()
{
    long long n;
    cin >> n;
    Euler(n + 10);
   //偶数求和
    long long sum = n / 2 * 2;
  //奇数求和
    for (int i = 3; i <= n; i += 2)
        sum += mp[i];
    cout << sum << endl;
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    // cin >> t;
    t = 1;
    while (t--)
        dilingtian();
    return 0;
}