感觉原来那篇文章已经卡的不行了，赶紧搬出来QAQ。

题目描述
【题意】
素数表如下：
2、3、5、7、11、13、17…………
有n次询问，每次问第几个素数是谁？
【输入格式】
第一行n(1<=n<=10000)
下来n行，每行一个整数pi，表示求第pi个素数。1<=pi<=100 0000
【输出格式】
每次询问输出对应的素数。
【样例输入】
3
1
4
7
【样例输出】
2
7
17

线性筛素数有两种，埃式筛和欧拉筛。

埃式筛

我们可以知道，一个数字如果不是质数，那么它的最小质因子一定小于等于这个数字的开平方。

很容易想到，不详细解释。

那么求(1)到(b)的素数的话，我们可以知道，(1)到(b)的合数的最小质因数也是一定小于等于(sqrt b)的，那么我们只需要求出(sqrt b)内的所有素数并且暴力for一遍，空间小，复杂度为(O(nloglogn))

for(int  i=2;i<=sqrt(b);i++)
{
    if(mp[i]==false)//为素数
    {
        for(int  j=i;j<=b;j+=i)mp[j]=true;
    }
}

给出一种神奇卡常版：

for(register  int  i=3;i<=sqrt(m);i+=2)
{
    if(a[i/2]==true)
    {
        for(register  int  j=i*3;j<=m;j+=i*2)a[j/2]=false;
    }
}

但是，还是可以优化的，每次跳的时候从(i^2)开始跳，因为前面的有更小的素数去更新。

for(int  i=2;i<=sqrt(b);i++)
{
    if(mp[i]==false)//为素数
    {
        for(int  j=i*i;j<=b;j+=i)mp[j]=true;
    }
}

这个的神奇卡常版就不加了QAQ。

复杂度正确，貌似是用调和级数来证，我不会QAQ。

欧拉筛

后面题目主要用欧拉筛，复杂度(O(n))

这个就很神奇了，先给出代码：

#include<cstdio>
#include<cstring>
#define  N  21000000
using  namespace  std;
int  ins[2100000];//素数表
bool  mp[N];
int  main()
{
	for(int  i=2;i<=20000000;i++)
	{
		if(!mp[i])ins[++ins[0]]=i;//存入素数表
		for(int  j=1;j<=ins[0]  &&  ins[j]*i<=20000000;j++)
		{
			mp[ins[j]*i]=true;
			if(i%ins[j]==0)break;
		}
	}
	int  n;scanf("%d",&n);
	for(int  i=1;i<=n;i++)
	{
		int  x;scanf("%d",&x);
		printf("%d
",ins[x]);
	}
	return  0;
}

许多人疑问这一句

if(i%ins[j]==0)break;

如果(ins_{j}|i)，那么就可以break了，Why？那么我们设(i)为(d*ins_{j})，设(k>j)，(i*ins_{k}=d*ins_{j}*ins_{k}=(d*ins_{k})*ins_{j})，我们可以知道(d*ins_{k}>d*ins_{j})，那么在以后的循环，(i*ins_{k})会被重复标记，那么此时就可以break了，一句话就这么精妙。

超级卡常版：

for(register  int  i=3;i<=m;i+=2)
{
    if(a[i/2]==true)b[++k]=i;
    for(register  int  j=1;j<=k  &&  b[j]*i<=m;++j)
    {
        a[b[j]*i/2]=false;
        if(i%b[j]==0)break;
    }
}

当然，慎用卡常版。

其实我是乱搞的

复杂度证明及其性质

对于合数(x)，设其最小的约数(y)，那么他有没有可能被大于(y)的约数所(z)找到呢？

那么就是(frac{x}{z}*z)，但是(y|frac{x}{z})，所以在找到(x)的时候就会退出，所以每个数字只会被其最小约数找到，所以就是(O(n))

另外提一下，因为其只能被最小约数筛，所以经常被用来筛积性函数。

还有一个性质也经常被用到：如果(i)被某个质数(x)整除（就是进入了(if)），那么(i*x)的某个质数因子的指数一定大于(1)。

欧拉筛筛积性函数

关于积性函数的定义可以去看“各种友(e)善(xin)数论总集，从入门到绝望4（狄利克雷卷积与莫比乌斯反演）”

对于一般的积型函数：(f(i)f(j)=f(ij))当(gcd(i,j)=1)。

我们可以对于每个数字(i)都存一个(low)值，表示的是最小的约数次幂，即对于一个数字拆成：(p_{1}^{a_{1}}...p_i^{a_i}(p_1<p_2<p_3<...))（(p)都是质数），那么(low)存的就是(p_1^{a_1})。

而当我们在找到一个质数的时候，就处理其次幂的函数值（这也是积性函数中最需要推的东西）。

所以一个数字(x)就可以被拆成(frac{x}{low_x})和(low_x)了。

而对于完全积性函数，不用存(low)值，而对于某些具有一定性质的完全积性函数，我们也可以采用某些神奇的仿写省掉(low)，常见的做法就是对于(i)被某个质数整除和没有被整除的情况分别讨论，如：(phi(φ))函数。

具体操作请参照欧拉函数。