质数：只能被1和他自己整除的数，也叫素数。

算法１：根据素数定义来找反例，在2~n-1之间找因子，如果能找到因子， 就证明该数不是质数

• 1 质数判断（乞丐版）

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int n;
	int flag = 0;//标志量 如果是合数1，质数0 
	cin >> n;
	for(int i = 2; i < n; i++){//2~n-1
		if(n % i == 0){//找到一个因素 
			flag = 1; 
			break;//跳出当前循环 
		}
	} 
	if(flag == 1) cout << "合数";
	else cout << "质数"; 
	return 0;
}

• 2 质数判断（小康版）

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int n;
	int flag = 0;//标志量 如果是合数1，质数0 
	cin >> n;
	for(int i = 2; i <= sqrt(n); i++){//2~sqrt(n)
		if(n % i == 0){//找到一个因素 
			flag = 1; 
			break;//跳出当前循环 
		}
	} 
	if(flag == 1) cout << "合数";
	else cout << "质数"; 
	return 0;
}

• 2质数判断（究极版）

//判断单个质数的最快方法 
#include<bits/stdc++.h>
using namespace std;

int main()
{
	int n;
	int flag = 0;//标志量 如果是合数1，质数0 
	cin >> n;
	for(int i = 2; i <= n / i; i++){ //2~n-1，这样写不容易溢出，而且要比sqrt快一些。
		if(n % i == 0){//找到一个因素 
			flag = 1; 
			break;//跳出当前循环 
		}
	} 
	if(flag == 1) cout << "合数";
	else cout << "质数"; 
	return 0;
}

• 质数判定的常用函数写法

bool prime(int x)
{
    if(x < 2) return 0;
    for(int i = 2; i <= x / i; i++) 
        if(x % i == 0) return 0;
    return 1;
}

算法２：埃拉托斯特尼筛法求素数（埃氏筛）O(n logn)

• 埃拉托斯特尼(公元前276~前194），古希腊数学家，天文学家，主要成就：很精确的测出了地球的周长。
• 思想：任意质数x的倍数2x,3x,...都不是素数。
• 做法：在内存中先预处理一个素数表，之后用 $O(1)$的复杂度就可以判定一个数是不是质数
• • 代码0：

#include<vector>
#include<iostream>
#include<cstring>
using namespace std;

bool a[10000005];
vector<int> v;
void sf_p(int x)
{
  a[0] = a[1] = 1;
  for(int i = 2; i <= x / i; i++)
    if(!a[i])
      for(int j = i + i; j <= x; j += i) a[j] = 1;
}

int main()
{
    int n;
    cin >> n;
  		sf_p(n);
    for(int i = 2; i <= n; i++)
        if(!a[i])
            v.push_back(i);
    cout << v.size() << endl;
    for(int i = 0; i < v.size(); i++)
        cout << v[i] << " ";
    cout << endl;
    return 0;
}

• • 代码1：

#include <iostream>
using namespace std;

//埃氏筛法
int pri[100005];
void primeT()
{
	pri[1] = 1;//打素数表， 是客观存在的 
	for(int i = 2; i <= 10000 / i; i++)
		if(pri[i] == 0)//当i已经被置1时，就不需再求i的倍数 
			for(int j = 2; i * j <= 100; j++)
				pri[i * j] = 1;
}
int main() 
{
	primeT();
	for(int i = 1; i <= 100; i++)
		if(pri[i] == 0) 
			cout << i << " ";
	return 0;
}

• 代码2：

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1000000;
bool is_p[N];
int prime[N/4];

int Eratosthenes(int n)
{
	int tot = 0; 
	memset(is_p, 1, sizeof is_p);//将数组标记为真，假设都是素数 
	//for(int i = 1; i <= n; i++) is_p[i] = 1;
	memset(prime, 0, sizeof prime);//清空存放素数的数组 
	is_p[0] = is_p[1] = 0;//将0，1标记为不是素数 
	for(int i = 2; i <= n; i++)//从2开始筛, 只要筛到n的平方根,如果要把素数存下来，要筛到n 
	{
		if(!is_p[i]) continue;//如果为假，就是被前面的数筛掉了， 不是素数 
		prime[++tot] = i;//没有筛掉，就是素数， 保存到素数数组中 
		for(int j = i + i; j <= n; j += i) 
			is_p[j] = 0;//将i的倍数标为假（筛掉） 
	}
	return tot; 
}
int main() 
{
	cout << Eratosthenes(N) << endl;
	return 0;
}

N	素数个数
100	25
1000	168
10000	1229
100000	9592
1000000	78498
10000000	664579
100000000	5761455

算法3：欧拉筛（线性筛）O(n)

• 埃氏筛存在的问题： 在筛的过程中，会存在的重复计算（如被做为2的倍数筛掉后， 在后面筛3，5...的倍数时， 还会再次被筛到，这就造成了浪费。
• 欧拉筛法的基本思想 ：在埃氏筛法的基础上，让每个合数只被它的最小质因子筛选一次，以达到不重复的目的。
• 欧拉（1707~1783）瑞士数学家、自然科学家。13岁时入读巴塞尔大学，“所有人的老师”，数学史上最多产的数学家， 各种欧拉公式。

i的值	质数表[数组]	筛去的数?
2		4
3	2,3	6,9
4		8
5	2,3,5	10,15,25
6		12
7	2,3,5,7	14,21,35,49
8		16
9		18,27

• 合数都可以分解成最小质因子乘以最大非自身因子的形式（n = prime[i] x i), 如24 = 2 x 12, 所以24在12时被筛去。每个合数只会被筛一次，所以复杂度是O(n)。

欧拉筛的算法步骤：

• 依次枚举每一个数。

• 若当前数没被筛掉，则把这个数加入质数集合

• 对于每一个数， 枚举当前已知质数，并相应筛掉当前数 x 枚举到的质数。而被筛掉的那个数的最小质因数一定是枚举到的质数。

• 如果i是枚举到的质数的倍数，停止枚举质数（这条保证了每个合数只会被筛一次）

• 算法0：

#include<vector>
#include<iostream>
#include<cstring>
using namespace std;

bool a[10000005];
int prime[1000005];
vector<int> v;
void o_p(int x)
{
  int cnt = 0;
  memset(a, 1, sizeof a);
  a[0] = a[1] = 0;
  for(int i = 2; i <= x; i++)
  {
    if(a[i] == 1)
      prime[cnt++] = i;
    for(int j = 0; j < cnt && prime[j] * i <= x; j++)
    {
      a[prime[j] * i] = 0;
      if(i % prime[j] == 0) break;
    }
  }
}

int main()
{
    int n;
    cin >> n;
  		o_p(n);
    for(int i = 2; i <= n; i++)
        if(a[i])
            v.push_back(i);
    cout << v.size() << endl;
    for(int i = 0; i < v.size(); i++)
        cout << v[i] << " ";
    cout << endl;
    return 0;
}

• 算法1：

#include <iostream>
#include <cstring>
using namespace std;

const int N = 10000;

bool is_prime[N];
int prime[N];

void o_prime(int n)//欧拉筛（线性筛） 
{
	int cnt = 0;
	memset(is_prime, 1, sizeof is_prime); 
	is_prime[0] = is_prime[1] = 0;
	for(int i = 2; i <= n; i++)
	{
		if(is_prime[i])
			prime[cnt++] = i;//加到质数数组里 
		for(int j = 0; j < cnt && prime[j] * i <= n; j++)//关键1 
		{
			is_prime[prime[j] * i] = 0;
			if(i % prime[j] == 0)//关键2 
				break; 
		} 
	}
}

int main() 
{
	o_prime(N);//筛出N以内的所有素数 
	int tot = 0;
	for(int i = 1; i <= 10000; i++)
		if(is_prime[i])
			tot++;
	cout << tot << endl; 
	return 0;
}

• 算法2：

#include<iostream>
using namespace std;
 
//欧拉筛法 
int v[100001000]; //v[i]=a代表数i的最小质因数为a 
int prime[600000]; 
int cnt=0;
 
void is_prime(int n){
	v[0]=v[1]=1;
	for(int i=2;i<=n;++i){ //注意这里也统计了等于n的数 
		if(!v[i]){ //从小到大枚举，能保证如果v[i]==0，那么i就是素数 
			v[i]=i;
			prime[++cnt]=i;
		}
		//注意一点，i显然永远是大于或等于prime[j]的，但 v[i] 不一定
		//而一个质数的最小质因数也就是其本身，即prime[j]的最小质因数是prime[j] 
		for(int j=1;j<=cnt;++j){
			//因为从小到大枚举，所以当前的大于，以后的一定大于 
			if(prime[j]>n/i||prime[j]>v[i])
				break; 
			v[i*prime[j]]=prime[j];
			// i*prime[j] 代表当前数乘以之前出现的素数
			// v[i*prime[j]] 的最小质因数是prime[j]
			// 当 i%prime[j]==0 时，显然成立
			// 当 i%prime[j]!=0 时，又由于上面的 if 判断保证了 v[i]>=prime[j]，所以也成立 
			
			/**
			解释上面的这个 if 判断条件
			第一个条件 prime[j]>n/i 用于防止越界
			第二个条件 prime[j]>v[i]，如果 i 的最小质因子比prime[j]的最小质因子小，那么
			v[i*prime[j]]应该等于v[i]，但是现在用当前数的最小质因子给 i*prime[j] 的最小质因子赋值会导致重复赋值，
			因为后面 i==(i*prime[j])/v[i] 的时候prime[i]能在不大于v[i]的情况下 v[i*prime[j]]=prime[j]
			也就是说，我们要保证prime[j]为最小质因子，这样能减少操作次数 */ 
		}
	}
} 
 
int main(){
	int n,q;
	cin>>n>>q;
	is_prime(n);
	for(int i=0;i<q;++i){
		int k;
		cin>>k;
		cout<<prime[k]<<endl;
	}
	return 0;
}

洛谷P3383 【模板】线性筛素数 参考资料出处