Forsaken喜欢数论

链接：https://ac.nowcoder.com/acm/contest/1221/A
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld

题目描述

        Forsaken有一个有趣的数论函数。对于任意一个数xxx，f(x)f(x)f(x)会返回xxx的最小质因子。如果这个数没有最小质因子，那么就返回0。

        现在给定任意一个nnn，Forsaken想知道∑i=1nf(i)\sum_{i = 1}^{n}{f(i)}∑i=1n​f(i)的值。

        

输入描述:

一个整数nnn。

输出描述:

一个整数代表上面的求和式的值。

示例1

输入

4

输出

7

备注:

1≤n≤3e71 \leq n \leq 3e71≤n≤3e7

思路:线性筛法可以求1到n每个数字的最小质因子
具体思路见注释

#include <iostream>

#include<bitset>

#include<algorithm>

#include<string>

#include<cmath>

using namespace std;

const int maxn= 3e7;

const int maxn1=1e6;

int primes[maxn], cnt;

bool st[maxn];

long long ans=;

void get_primes(int n)

{

    for (int i = ; i <= n; i ++ )

    {

        if (!st[i]) primes[cnt ++ ] = i,ans+=i;//如果一个数本身是质数，最小质因子就是它本身

        for (int j = ; primes[j] <= n / i; j ++ )

        {

            st[primes[j] * i] = true;

            ans+=primes[j];//对于响primes[j] * i这样不是质数的数字，那么primes[j]正好是他的质因子

            if (i % primes[j] == ) break;

        }

    }

}

int main()

{

    int n;

    cin >> n ;

    get_primes(n);

    cout << ans << endl;

    return ;

}