素数判断

bool is_prime(int u) {
	if (u == 0 || u == 1)return false;
	if (u == 2)return true;
	if (u % 2 == 0)return false;
	for (int i = 3; i <= sqrt(u); i += 2)
		if (u%i == 0)return false;
	return true;
}

普通筛法

时间复杂度是 O(nloglogn)，不足之处在于一个合数可能被筛选多次。

#include<bits/stdc++.h>
using namespace std;
const int N = 2000005;
int prime[N], num = 0;//prime存素数 
bool p[N] = { 0 };//p存是否被筛除 
void find_prime()
{
	p[0] = p[1] = true;
	for (int i = 2; i < N; i++)//筛选2~maxn内的素数 
	{
		if (p[i] == false)//没被筛除的（即为素数）记为false,被筛除的为true 
		{
			prime[num++] = i;//i为素数加入数组 
			for (int j = i + i; j < N; j += i)//筛除i的倍数 
			{
				p[j] = true;
			}
		}
	}
}

线性筛

时间复杂度为 O(n)，原因在于每个合数保证只被它最小的那个质因子筛选。关键代码在第 10，11 行，因为如果 i 能整除 prime[j]，那么 i 肯定是个合数，且 i 中有质因子肯定小于等于 prime[j]，所以到此就可以停止了，因为后面的 prime[]会比 i 小的那个质因子要大。

const int N = 2000005;
int prime[N], num = 0;//prime存素数 
bool p[N] = { 0 };//p存是否被筛除 
void find_prime() {
	p[0] = p[1] = 1;
	for (int i = 2; i < N; i++) {
		if (!p[i])
			prime[num++] = i;
		for (int j = 0; j < num && prime[j] * i < N; j++) {
			p[i*prime[j]] = 1;
			if (i % prime[j] == 0)
				break;
		}
	}
}