判断素数的方法

1.最直接的筛法

void get_Prime()
{
    prime[++c] = 2; 
    for(int i=3;i<=n;i+=2)   //素数肯定是奇数
    {
        int flag = 0;  //判断i是不是素数标记
        for(int j=2;j*j<=sqrt(i);++j)   //判断i有没有其他因数
        {
            if(i%j==0)  //如果i还有其他因数
            {
                flag = 1;  //i不是素数
                break;    
            }
        }
        //没有找到可以分解的因数，说明是素数
        if(!flag) prime[++c] = i;
    }
}

时间复杂度为O(n*sqrt(n))

2.埃氏筛

void get_prim()
{
	for(int i=2;i<=n;i++)
	{
		if(!vis[i])//vis数组超前记录合数，如果当前值i被记录过说明是合数，否则一定为质数
		{
			prim[++cnt]=i;//记录质数
			for(int j=i*i;j<=n;j+=i)//向后遍历，找到以i为因数的所有合数
			vis[j]=1;
		}
	}
	return ;
}

时间复杂度为O(nloglogn),其中loglogn可以近似为一个常数。
同一个合数可能会被重复记录，例如2会标记2，4，6，8，10，12，14，16，18，
3会标记3，6，9，12，15，18。
12和18被重复标记，这也是loglogn形成的原因。

3.欧拉筛（线性筛)

欧拉筛是基于埃氏筛的优化

void get_prim()
{
	for(int i=2;i<=n;i++)
	{
		if(!vis[i])prim[++cnt]=i;
		for(int j=1;prim[j]*i<=n;j++)
		{
			vis[prim[j]*i]=1;
			if(i%prim[j]==0)break;
		}
	}
	return ;
}

解释：
1.从小到达枚举每个数，如果这个数没有被记录在vis数组，则一定是质数。
2.枚举每个记录过的质数prim[j]，
（1）将合数prim[j]*i记录在vis数组中。
（2）i%prim[j]保证一个合数只被最小质因子划掉，从而保证每个合数只会被记录依次，从而消除了埃氏筛的loglogn，实现了优化。
对于一个质数i，prim[j]最多枚举到自身。
对于一个合数i，prim[j]最多枚举到i的最小质因数。

时间复杂度O(n)

【模板】线性筛素数

题目背景

本题已更新，从判断素数改为了查询第 $k$ 小的素数
提示：如果你使用 cin 来读入，建议使用 std::ios::sync_with_stdio(0) 来加速。

题目描述

如题，给定一个范围 $n$，有 $q$ 个询问，每次输出第 $k$ 小的素数。

输入格式

第一行包含两个正整数 $n,q$，分别表示查询的范围和查询的个数。

接下来 $q$ 行每行一个正整数 $k$，表示查询第 $k$ 小的素数。

输出格式

输出 $q$ 行，每行一个正整数表示答案。

样例 #1

样例输入 #1

100 5
1
2
3
4
5

样例输出 #1

2
3
5
7
11

提示

【数据范围】
对于 $100\%$ 的数据，$n=10^8$，$1\le q\le 10^6$，保证查询的素数不大于 $n$。

Data by NaCly_Fish.

代码实现

#include<iostream>
using namespace std;
#define MAX_N 100000000
#define MAX_K 1000000
int prim[MAX_N+5];
int vis[MAX_N+5];
int ind[MAX_K+5];
int n,q,cnt=0;
void get_prim()
{
	for(int i=2;i<=n;i++)
	{
		if(!vis[i])prim[++cnt]=i;
		for(int j=1;prim[j]*i<=n;j++)
		{
			vis[prim[j]*i]=1;
			if(i%prim[j]==0)break;
		}
	}
	return ;
}
int main()
{
	cin>>n>>q;
	for(int i=1;i<=q;i++)scanf("%d",&ind[i]);
	get_prim();
	for(int i=1;i<=q;i++)cout<<prim[ind[i]]<<endl;
	return 0;
}

>素数练习题<