猫史档案馆

这里讲的只是小学奥数的亿点拓展而已，推导鬼畜，代码感人，学习愉悦。

素数筛问题

简单地说，素数筛问题就是让你求一个区间内的素数。

有如下几种类型:

1.求素数个数

2.求第k个素数

等等。

原始解法

我们有一种极为喵的解法，O(n^2)。

枚举每个数，从2开始枚举每个小于此数的数。如果这个数是外层枚举的那个数的约数，表示外层枚举的数是合数，打上标记。

#include<bits/stdc++.h>
using namespace std;
int i,j,k,n,a[1000005],prime[1000005],cnt,q;
int main(){
	cin>>n>>q;
	for(i=2;i<n;i++)
		for(j=2;j<i;j++)
			if(!(i%j))a[i]=1;
	for(i=2;i<n;i++)
		if(!a[i]){
            cnt++;prime[cnt]=i;
        }
    while(q--){cin>>k;cout<<prime[k]<<endl;}
	return 0;
}

这代码绝对妥妥的T了~

怎么办？问题出在哪里？

（评测机）

当然不是。

考虑优化：对于任意一个正整数n，必然有小于sqrt(n)（根号n）的约数。

因此，只需枚举j，只需要到j*j<=i就行了。

#include<bits/stdc++.h>
using namespace std;
int i,j,k,n,a[1000005],prime[1000005],cnt,q;
int main(){
	cin>>n>>q;
	for(i=2;i<n;i++)
		for(j=2;j*j<=i;j++)
			if(!(i%j))a[i]=1;
	for(i=2;i<n;i++)
		if(!a[i]){
            cnt++;prime[cnt]=i;
        }
    while(q--){cin>>k;cout<<prime[k]<<endl;}
	return 0;
}

结果呢？还是TLE。（一盆冷水）

问题出在哪？

（评测机）

因此，我们需要使用——筛法

Eratosthenes 筛

这个筛法也是很原始的。

从2 开始，将每个数的各个倍数，标记成合数。

范围内所有未被标记的数，就是所求的全部素数。

for (int i = 2; i <= n; i++)
    isPrime [i] = true;
for (int i = 2; i <= n; i++)
    for (int j = i+i; j <= n; j+=i)
        isPrime [j] = false ;

然而这个代码还需要很多优化！（两盆冷水）

考虑优化：任一合数都是某个质数的倍数

所以只需要用质数去筛即可。

for (int i = 2; i <= n; i++)
    isPrime [i] = true;
    for (int i = 2; i <= n; i++)
        if ( isPrime [i]) {
            for (int j = i+i; j <= n; j+=i)
        isPrime [j] = false ;
    }

容易知道复杂度是

虽然很难证明，但是

很显然，这个代码仍然需要很多优化。

事实上一个n 以内的数若是合数，必然有不大于sqrt(n)的约数. 且若发现一个质数p，也不应该从2 * p 开始筛起，应该从p * p 筛起，因为更小的合数已经被别的质数筛掉了。

for (int i = 2; i <= n; i++)
    isPrime [i] = true;
    for (int i = 2; i*i <= n; i++)
        if ( isPrime [i]) {
            for (int j = i*i; j <= n; j+=i)
                isPrime [j] = false ;
        }

这个代码已经很优秀了。但是不幸的是，还有更好的方法。

这就需要用到

Euler 筛（线性筛）

之前的筛法，一个合数会被筛去多次（被它的每个质因数筛一次）

如果我们能保证每个合数只被筛一次，就能得到时间复杂度为线性的筛法。

Euler 筛就是这样的筛法，它保证每个合数只被其最小质因数筛去。

for (int i = 2; i <= n; i++) {
    if ( isPrime [i]) prime . push_back (i);
        for (int j = 0; j < prime .size (); j++) {
            if (i * prime [j] > N) break ;
            isPrime [i * prime [j]] = false ;
            if (i % prime [j] == 0) break ;
        }
}

当然每次被最大的质因数筛掉也是可以的：

for(int i=2;i<=n;i++)
{
	if(!check[i])prime[cnt++]=i;//若当前数i没有被之前的所有数筛掉，表明i是素数，将i添加进素数表prime
	for(int j=0;j<cnt&&i*prime[j]<100000001;j++)//注意i*prime[j]不要超过n的上限（10^8）
	{
		check[i*prime[j]]=1;//将当前素数prime[j]的i倍标记为合数
		if(i%prime[j]==0)break;//关键步骤：保证每个合数只被筛一次
	}
}

恭喜你，这个算法可以算是比较优的了。

下面讲解积性函数

积性函数

积性函数指对于所有互质的整数a和b有性质f(ab)=f(a)f(b)的数论函数。