素数筛法

发表于 | 更新于 | 分类于

Eratosthenes筛法(实用)

时间复杂度: $\sum_{质数 p <= N * {\frac Np}} = O(NloglogN) $

思想:

定义一个bool v数组表示是否是合数
对于一个从2开始的整数，它的倍数(从2开始)都将是合数，将其全部筛去，剩下的即是素数。

优化

对于一个数x，我们可能多次筛它，那么考虑 直接从$ x^2 $开始筛，因为
在$ x^2 $ 之内的数已经被前面$(x - 1) x$筛掉了，所以从 ${x ^ 2} -> {x * k} (k <= n) $

1
2
3
4
5
6
7
8
9
10
11
12

const int N = 100;
int v[N], m;		//v为访问数组
void primes(int n)
{
	for(int i = 2; i <= n; i ++ )
	{
		if(v[i])	continue;
		for(int j = i; j <= n / i; j ++ )	//从i^2 开始筛
			v[i * j] = 1;
	}
}

线性筛法

思想:

“从大到小累积质因子” 设数组v记录每个数的最小质因子

方法

  • 若v[i] == 0, 则i是质数(最小质因数是它本身)，记录在prime数组
  • 用每个不大于v[i]的质数p，与i相乘构成新的合数，由于p <= v[i]
    此时新数的最小质因数为p

时间复杂度分析

每个数会被它的最小质因数筛一次, 时间复杂度为 $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const int N = 100;
int v[N], m;		//v数组记录每个数的最小质因数
int prime[N];
void primes(int n)
{
	for(int i = 2; i <= n; i ++ )
	{
		if(!v[i])			//最小质因数是他本身，记录答案
			v[i] = i, prime[ ++ m] = i;
		for(int j = 1; j <= m; j ++ )		//用小于v[i]的p去乘i
		{
			if(!(prime[j] <= v[i] && prime[j] <= n / i))	continue;		
							//p > v[i] 或 p * i > n则退出
			v[i * prime[j]] = prime[j];			//最小质因子筛数
		}
	}
}

欧拉函数

设n分解的质因数形式为$n= a_1^n1 a_2^n2 a_3^n3 …… a_n^n$
那么在1-n-1中与n互质的个数为
cnt = n (1 – 1 / a1) (1 – 1 / a2) …… * (1 – 1 / an)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int euler(int n)
{
	  int res = n;
	  for(int i = 2; i * i <= res; i ++)
	  {
		  if(n % i == 0)				//如果有这个质因数
           res = res / i * (i-1);		//防止溢出，先除再乘
        while(n % i == 0)				//除去相同的因子，因为只需一次即可
			 n /= i;
}
	if(n! = 1)						//可能因子超过 根号n
		res = res / n * (n - 1);			//再乘上它的1- 1/num
	return n;
}
0%