每个人都知道Arup喜欢素数！ 这就是为什么他在UCF教授密码学课程。 最近，Arup对大于1的正整数n定义了以下函数：
f（n)是的n最小质因子。
例如，f（14）= 2，f（15）= 3，f（16）= 2和f（17）= 17。
使用此函数，我们可以生成一系列项f（s），f（s + 1），f（s +2），…，f（e），其中s表示开始函数输入，e表示结束函数 输入。
奥雅纳（Arup）认为这些序列很有趣，但是他真正好奇的是找到其中一个序列中k个最小元素的总和。 你能写一个程序来帮助他吗？
给定s，e和k，找到序列f（s），f（s + 1），f（s +2），…，f（e）中的k个最小值的总和。
第一行也是唯一的输入行将包含三个正整数，即s（2≤s≤1e18），e（s +100≤e≤s + 106）和k（1≤k≤0.9 *（e – s + 1） ），分别代表开始函数输入，结束函数输入和要累加的最小项数。
单独在一行上打印指定序列的k个最小项的总和。
样例1】
100200 70
【样例2】
213419169
样例输出复制
【样例1】
165
【样例2】
546
提示
即使输入规范不允许将“ 14 17 3”作为输入条件（即，该条件将不在判断数据中），但您还是可能希望将其用于测试目的，这是一个简单的情况-输出（7 ）可以在纸上轻松验证。 （顺便说一句，预期的解决方案无论如何应能正确解决此问题。）
题目意思：就是定义了一个f(n)就是n的最小质因子，给你一个s,e,k,就是找区间s到e中所有f(n)排序后最小的k个。但是s，e,很大
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 5000010; int f[N]; int prime[N],cnt; bool vis[N]; bool dabiao[N]; void get_prime() { for(int i=2;i<N;i++) { if(!vis[i]) prime[cnt++] = i,f[i]=i; for(int j=0;prime[j]*i<N;j++) { if(!f[prime[j]*i]) f[prime[j]*i]=prime[j]; vis[i*prime[j]]=true; if(i%prime[j]==0) break; } } } void qujianshai(ll l,ll r){ memset(f,0,sizeof f); for(ll i=0;i < cnt&&prime[i]*prime[i]<=r;i++){ for(ll j=max(2LL,(l+prime[i]-1)/prime[i])*prime[i];j<=r;j+=prime[i]){ if(j>=l){ dabiao[j-l]=1;//1是合数 if(f[j-l]==0) f[j-l] = prime[i]; } } } } ll st[N],t; int main() { get_prime(); ll s,e,k; f[1]=1; cin>>s>>e>>k; qujianshai(s,e); for(ll i=0;i<=e-s;i++){ if(dabiao[i]==0){ st[++t]=i+s; } else{ st[++t]=f[i]; } } sort(st+1,st+t+1); ll ans=0; for(int i=1;i<=k;i++){ ans+=st[i]; } cout<<ans<<endl; return 0; }