题目描述
定义p(n)为n大于1的最小约数。
给出N，求p(2)+p(3)+...+p(N)的值。
给出N，求p(2)+p(3)+...+p(N)的值。
输入
一个整数N。
输出
1个整数，表示所求的值。
样例输入
10
样例输出
28
提示
•对于30%的数据，N≤103；
•对于60%的数据，N≤103；
•对于100%的数据，2≤N≤107。
题目大意：略
思路：简单模拟一下过程，就会发现很像筛法求素数的过程。
先附上筛法求素数模板：
#include<cstdio> #include<cstring> #define ll long long int n;//求1-n的素数 bool prime[10000010]; void primejudge(){ memset(prime,true,sizeof(prime)); prime[0]=prime[1]=false; for(ll i=2;i*i<=n;i++){ if(prime[i]){ for(ll j=i*i;j<=n;j=j+i){ prime[j]=false; } } } } int main() { scanf("%d",&n); primejudge();//最终素数的判断结果储存在prime数组中 return 0; }
AC代码：
#include<cstdio> #include<cstring> #define ll long long int n; ll ans=0; bool prime[10000010]; void primejudge(){ memset(prime,true,sizeof(prime)); for(ll i=2;i<=n;i++){ if(prime[i]){ ans+=i; for(ll j=i*i;j<=n;j=j+i){ if(prime[j]) ans+=i; prime[j]=false; } } } printf("%lld\n",ans); } int main() { scanf("%d",&n); primejudge(); return 0; }