埃氏筛法-筛选素数_素数筛

某些题目可能需要求得n以内的所有素数
假设如下遍历一个个判定是否素数， 当n较大可能超时

bool is_prime(int n)
{
	for(int i = 2; i * i <= n; i++)
		if(n % i == 0) return false;
	return n != 1;			//1是例外
}

1
2
3
4
5
6
7

埃氏筛法
将2到n范围内的数字全部记录下来， 此时最小数字2是素数， 将数字中2的倍数全部删除， 此时最小数字是3， 将数字中3的倍数全部删除， 以此类推， 得到n范围内的全部素数。时间复杂度仅为O(nloglogn).

int prime[maxn];    //用于保存maxn以内的所有素数
bool is_prime[maxn + 1];		//is_prime[i] == true, i为素数

//函数返回n以内的素数个数
int get(int n)
{
	int p = 0;
	fill(is_prime + 2, is_prime + n + 1, true);			//将2到n的范围内设置为true， 因为0， 1 非素数
	for(int i = 2; i <= n; i++)
	{
		if(is_prime[i])
		{
			prime[p++] = i;
			for(int j = 2 * i; j <= n; j += i) is_prime[j] = false;
		}
	}

	return p;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19