素数筛 -- 埃氏筛 欧拉筛 详解
素数筛
什么是质数？
若a ,b 除±1外无其他公因数，则称a和b互质。
定理1（算术基本定理）
任意正整数n（n != 1）恰有一种方法写成质数的乘积（不计因数乘积的顺序）
定理2（欧几里得）
质数无穷多
那么我们初学任意编程语言时，一定会遇到求素数的问题，我们朴素的方法一般都是暴力枚举
inline bool isprime(int x)
{
for (int i = 2; i < x; i++)
if (x % i == 0)
return false;
return true;
}
从2枚举到 x - 1，如果整除那么就不是素数
代码的正确性毫无疑问 ， 但是如果需求量过大，效率就显得低下
这时有人会发现，我们没必要枚举到x - 1，我们只需要枚举到它的平方根即可
(小的那个因数整除，大的必然整除)
如此一来，代码就变成了这个样子
inline bool isprime(int x)
{
int sq = (int)sqrt(x);
for (int i = 2; i < sq + 1; i++)
if (x % i == 0)
return false;
return true;
}
优化掉sqrt的二分快速幂的复杂度的话
inline bool isprime(int x)
{
for (int i = 2; i <= x / i; i++)
if (x % i == 0)
return false;
return true;
}
可这样仍然不能满足我们对于效率的要求，显然我们还要另寻出路。
空间换时间是我们算法优化中的一个重要思想，记忆化搜索就是该思想的一种应用
我们每判定出一个素数，对于这个素数乘上大于1的因子的数显然都是合数，如果我们能标记这些合数，我们就能省略去许多
不必要的判断
const int maxn = 1e7 + 10;
int prime[maxn + 1];
inline bool isprime(int x)
{
prime[2] = 0;
for (int i = 2; i <= maxn / i; i++)
{
if (!prime[i])
for (int j = i * i; j <= maxn; j += i)
prime[j] = 1;
}
return !prime[x];
}
这就是我们的埃氏筛
这里解释为什么埃氏筛的j要从i * i而不是2 * i开始， 因为对于大于2的i ， 任意 k * i（k < i)它一定在筛k 的 质因数的时候筛过了
这也是我们接下来进一步优化的思想
其实这样我们的时间优化已经大大提升了，可是我们发现我们对于每个合数都筛选到x这样一定有重复的情况
比如对于36 ， 它可以被4筛 可以被9筛等等，就像kmp算法next数组优化为nextval一样， 我们的埃氏筛也有需要优化的地方
我们先上代码
const int maxn = 1e7 + 10;
int primes[maxn + 1], cnt = 0;//0为素数 1为合数
int prime[maxn + 1];
inline bool isprime(int x)
{
prime[2] = 0;
for (int i = 2; i <= maxn; i++)
{
if (!prime[i])
primes[cnt++] = i;
for (int j = 0; j <= cnt && primes[j] * i < maxn; j++)
{
prime[primes[j] * i] = 1;
if (i % primes[j] == 0)
break;
}
}
return !prime[x];
}
这就是素数筛的终极版--欧拉筛
那么为什么欧拉筛能保证每个合数都被筛且只被筛一次呢
还记得我们的定理1（算术基本定理）吗
定理1（算术基本定理）**
任意正整数n（n != 1）恰有一种方法写成质数的乘积（不计因数乘积的顺序）
欧拉筛法核心思想：每个合数只被自己的最小质因子筛一次。
我们prime[i]是从最小的素数开始枚举
i%prime[j] != 0 则说明prime[j]就是我的最小质因数
对 i%prime[j]==0 时即跳出循环的解释：此时可以令 i = k×prime[j]，若不跳出，继续筛 i×prime[j+1] 的话，i×prime[j+1] = k×prime[j]×prime[j+1]，它的最小质因子显然是 prime[j] 而不是 prime[j+1]，违反了筛法原则。
这样就保证了每个合数被最小质因数筛选一次