素数筛（埃氏筛+欧拉筛）

居然是一道模板题，院赛时就只知道暴力打表，发现毫无规律，然后暴力预处理，结果肯定TLE。。。。。，学长讲题解时，发现原来是数论中的：

素数筛：
于是赛后去学习了下素数筛，主要有两种方法
一、埃氏筛；二、欧拉筛

一、埃氏筛

思想：对于不超过n的每个非负整数p，删除是p的整数倍的数，当处理完这些数之后，还没被删除的数就是素数。

代码如下：

#include<bits/stdc++.h> #define maxn 100 using namespace std; int vis[maxn+10]; //判断是不是素数 int prime[maxn+10]; //存放素数的数组 int main() { memset(vis,0,sizeof(vis)); int m=0; for(int i=2;i<=maxn;i++) { if(vis[i]==0) prime[m++]=i; for(int j=i*2;j<=maxn;j+=i) vis[j]=1; } for(int i=0;i<m;i++) cout<<prime[i]<<endl; return 0; } 

改进：p可以限定为素数——只需在第二重循环前加一个判断if(vis[i]==0)即可

代码如下：

#include<bits/stdc++.h> #define maxn 100 using namespace std; int vis[maxn+10]; int prime[maxn+10]; int main() { memset(vis,0,sizeof(vis)); for(int i=2;i<=maxn;i++) { if(vis[i]==0) { for(int j=i*i;j<=maxn;j+=i) vis[j]=1; } } int m=0; for(int i=2;i<=maxn;i++) { if(vis[i]==0) prime[m++]=i; } for(int i=0;i<m;i++) cout<<prime[i]<<endl; return 0; } 

二、欧拉筛

思路：因为prime[]数组中是按从小到大顺序存储，当i能整除prime[j]，那么i*prime[j+1]这个合数肯定被prime[j]乘以某个数筛掉。（其实我是没搞太明白）

代码如下：

#include<bits/stdc++.h> #define maxn 100 using namespace std; int vis[maxn+10]; int prime[maxn+10]; int main() { memset(vis,0,sizeof(vis)); int m=0; for(int i=2;i<=maxn;i++) { if(vis[i]==0) prime[m++]=i; for(int j=0;j<m&&prime[j]*i<=maxn;j++) vis[prime[j]*i]=1; } for(int i=0;i<m;i++) cout<<prime[i]<<endl; return 0; } 

ps:以上都是求100以内素数的代码样例

XP的数论

题目描述

XP对数论非常不感冒，有一天，XSW向他提出这样一个问题：现在给定一个函数f(x)，设x的所有素因子个数为k(1不是素数,x本身可以算作它的因子)，则f(x) = (-1)^k，设S(x) = S(x-1) + x*f(x)，其中S(1) = f(1)，现在给定一个N，你的目的是要求出S(N)的值。XP学长对于XSW提出的这个问题有些迷茫，所以现在请你来解决这个问题。

输入

输入包含多组测试用例，第一行输入一个T表示测试数据组数，(1<=T<=100)
每组测试数据输入一个N，(1<=N<=10^5)

输出

上述S(N)的值。

样例输入

1
5

样例输出

-13

提示
样例中，我们首先可以知道f(1) = 1，f(2) = -1，f(3) = -1，f(4) = -1，f(5) = -1，因此S(5) = 1 - 2 - 3 - 4 - 5 = -13。

于是三种算法AC代码如下：

一：普通埃氏筛

#include<bits/stdc++.h> #define maxn 100000 using namespace std; int vis[maxn+10]; int prime[maxn+10]; int s[maxn+10]; int main() { memset(vis,0,sizeof(vis)); int m=0; for(int i=2;i<=maxn;i++) { if(vis[i]==0) prime[m++]=i; for(int j=i*2;j<=maxn;j+=i) { vis[j]=1; } } //for(int i=0;i<10;i++) // cout<<prime[i]<<endl; //cout<<endl; s[1]=1; for(int i=2;i<=maxn;i++) { int sum=0; for(int j=0;j<m&&prime[j]<=i/2;j++) { if(i%prime[j]==0) sum++; } if(vis[i]==0) sum++; if(sum%2==0) s[i]=s[i-1]+i; else s[i]=s[i-1]-i; } //for(int i=1;i<=10;i++) // cout<<s[i]<<endl; int t; scanf("%d",&t); while(t--) { int n; scanf("%d",&n); printf("%d\n",s[n]); } return 0; } /** 2 3 5 7 11 13 17 19 23 29 1 -1 -4 -8 -13 -7 -14 -22 -31 -21*/ 

二、改进后的埃氏筛

#include<bits/stdc++.h> #define maxn 100000 using namespace std; int vis[maxn+10]; int prime[maxn+10]; int s[maxn+10]; int main() { memset(vis,0,sizeof(vis)); int m=0; int num=sqrt(maxn+0.5); for(int i=2;i<=num;i++) { if(vis[i]==0) { for(int j=i*i;j<=maxn;j+=i) vis[j]=1; } } for(int i=2;i<=maxn;i++) { if(vis[i]==0) prime[m++]=i; } //for(int i=0;i<10;i++) // cout<<prime[i]<<endl; //cout<<endl; s[1]=1; for(int i=2;i<=maxn;i++) { int sum=0; for(int j=0;j<m&&prime[j]<=i/2;j++) { if(i%prime[j]==0) sum++; } if(vis[i]==0) sum++; if(sum%2==0) s[i]=s[i-1]+i; else s[i]=s[i-1]-i; } //or(int i=1;i<=10;i++) // cout<<s[i]<<endl; int t; scanf("%d",&t); while(t--) { int n; scanf("%d",&n); printf("%d\n",s[n]); } return 0; } 

三、欧拉筛

#include<bits/stdc++.h> #define maxn 100000 using namespace std; int vis[maxn+10]; int prime[maxn+10]; int s[maxn+10]; int main() { memset(vis,0,sizeof(vis)); int m=0; for(int i=2;i<=maxn;i++) { if(vis[i]==0) prime[m++]=i; for(int j=0;j<m&&prime[j]*i<=maxn;j++) { vis[prime[j]*i]=1; } } s[1]=1; for(int i=2;i<=maxn;i++) { int sum=0; for(int j=0;j<m&&prime[j]<=i/2;j++) { if(i%prime[j]==0) sum++; } if(vis[i]==0) sum++; if(sum%2==0) s[i]=s[i-1]+i; else s[i]=s[i-1]-i; } //for(int i=1;i<=10;i++) // cout<<s[i]<<endl; int t; scanf("%d",&t); while(t--) { int n; scanf("%d",&n); printf("%d\n",s[n]); } return 0; } 

不知道为什么，我写的三份代码居然跑起来时间差不多。。。。。。。