素数是指恰好有两个约数的整数（1和其本身）。

简单素性测试

因为n的约数都不超过n，所以只需检查2n-1的所偶整数是否整除n就能判定n是否为素数。进而，如果d是n的约数，那么n/d也是n的约数。由n=d×n/d可知min(d,n/d)≤sqrt(n)，所以只要检查 **2sqrt(n)** 得到所有整数就可以了。由此可知，整数分解和约数枚举都可以在 O(sqrt(n)) 时间内完成。


埃氏筛法

要枚举n以内的素数，可以用埃氏筛法。

  1. 首先，将2到n范围内的所有整数写下来。

  2. 其中最小的数字2是素数。将表中所有2的倍数都划去，

  3. 表中剩余的最小数字是3，他不能被更小的数长出，所以是素数。在将表中所有3的倍数都划去。

  4. 以此类推，如果表中剩余的最小数字是m时，m就是素数。然后将表中所有m的倍数划去。像这样反复操作，就能一次枚举n以内的素数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int prime[MAX_N];//第i个素数
bool is_prime[MAX_N+1]//is_prime[i]为true表示i时素数

//返回n以内素数的个数
int sieve(int n){
	int p = 0;
	for(int i = 0; i <= n; i++)
		is_prime[i] = true;
	is_prime[0] = false;
	is_prime[1] = false;
	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;
}

时间复杂度：O(nlognlogn)


区间筛法

对于求[a,b)区间内素数的问题可以采用区间筛法，即将埃氏筛法运用于[a,b)上。

先分别做好[2,sqrt(b))和[a,b)的素数表，在从[2,sqrt(b))中筛得素数时，也将其倍数从[a,b)的表中划去，最后剩下的就是区间[a,b)内的素数了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
typedef long long  ll;
bool is_prime[MAX_L];
bool is_prime_small[MAX_SQRT_B];

//对于区间[a,b)内的整数执行筛法。is_prime[i - a] ⇔ i是素数
void segment_sieve(ll a, ll b){
	for(int i= 0; (ll)i * i < b ; i++)
		is_prime_small[i] = true;
	for(int i = 2; i < b - a;  i++)
		is_prime[i] = true;

	for(int i = 2; (ll) i * i< b; i++){
		if(is_prime_small[i]){
			for(int j = 2 * i; (ll)j * j < b; j += i)
				is_prime_small[j] = false; //筛[2，sqrt(b))
			for(ll j = max(2LL, (a + i -1) / i) * i; j < b; j += i)
				is_prime[j - a] = false; //筛[a,b);
		}
	}
}