蓝桥杯1140 最小质因子之和(Hard Version)

题目描述

定义 F(i) 表示整数 i 的最小质因子。现给定一个正整数 N，请你求出 。

输入描述

第 1 行为一个整数 T，表示测试数据数量。

接下来的 T 行每行包含一个正整数 N。

1≤T≤，2≤N≤2×。

输出描述

输出共 T 行，每行包含一个整数，表示答案。

输入输出样例

示例 1

输入

3
5
10
15

输出

12
28
59

 

#include<iostream>
using namespace std;typedef long long ll;
const int N = 2e7+10;
int t;ll prime[N];  //存储所有筛出的质数
bool is_prime[N];  //状态数组，is_prime[i]为 1表示 i为质数
ll cnt;  //质数的个数 
ll sum[N];  //f[i]表示从2到i的所有数的最小质因子之和//线性筛： 
void f(int n)
{for(int i=2; i<=n; ++i){is_prime[i]=1;  //初始化：默认所有数为质数}for(int i=2; i<=n; ++i){if(is_prime[i]){cnt++;prime[cnt]=i;}for(int j=1; j<=cnt; ++j){int p = prime[j];if(i*p > n) break;is_prime[i*p] = 0;if(i%p == 0) break;}}
}int main()
{cin>>t;f(N);//预处理前缀和数组sumfor(int i=2; i<=N; ++i){if(is_prime[i]){sum[i] += sum[i-1]+i;  //是质数最小质因子就是该数本身}else {int j;for(j=1; j<=cnt; j++){if(i%prime[j]==0) break;  //否则就找最小质因子}sum[i] += sum[i-1]+prime[j]; }} while(t--){int n;        cin>>n;cout<<sum[n]<<endl;}return 0;
}