线性筛法

线性筛法

上节课讲的是 Eratosthenes 筛法利用的原理是 任意整数 x 的倍数 2x，3x，... 等都不是质数 。

但是即便如此也会有重复标记的现象，例如12既会被2又会被3标记，在标记2的倍数时，\(12 = 6*2\)，在标记3的倍数时，\(12 = 4*3\) ，根本原因是没有找到唯一产生12的方式。

线性筛法的核心原理

质数线性筛，每个合数必有一个最大因子（不包括它本身），用这个因子把合数筛掉

换言之：每个合数必有一个最小素因子，用这个因数把合数筛掉

过程

假设 i 是合数 t 的最大因数，t显然可能不唯一（例如 30 和 45 最大因数都是 15）。但是仔细想一想，必然有

线性插值法简单解释，t = i * p(p为小于 i 的质数) 。

• p为什么比 i 小？因为 i 是 t 的最大因数。
• 为什么 p 一定是质数？因为如果 p 是合数，那么 i 就一定不是 t 的最大因数，因为 p 可以再拆成若干素数相乘，这些素数再与 i 相乘会使因数更大。

既然如此，我们只需要把所有小于 i 的质数 p 都挨个乘一次好了。可是，真相真的是这样的嘛？

其实不是的，一不小心就忘记了最初的条件。我们要满足 i 是 t 的最大因数。如果 p 大于 i 的最小质因数，那 i 还是 t 的最大因数嘛？显然不是，任何一个合数都能唯一分解为有限个质数的乘积，除去这其中最小的质因数，其他的都乘起来就是最大因数 i 。所以我们不能让 p 大于 i 的最小质因数。

欧拉线性筛？下面有两个版本，核心处理稍有一点点不同，理解即可。

版本一

• v[i] 表示 i 的最小质因数。如果i就是质数，那么v[i] = i
• prime[j] 表示第 j 个质数。与之前的筛法不同，这个数组是存放质数的，而不是标记质数的

#define MAXN 1000000
int prime[MAXN],v[5*MAXN];
int m=0;//m表示现在筛出m个质数
void primes()
{for(int i=2;i<MAXN;i++){if(v[i]==0)//如果v[i]为0，说明 i 之前没有被筛到过，i 为质数{v[i] = i;prime[++m] = i;}for(int j = 1;j<=m;j++)//遍历小于 i 的所有质数{//如果质数大于 i 的最小质因数或者乘起来大于MAXN就跳出循环if(prime[j] > v[i] || prime[j] > MAXN/i) break;v[i*prime[j]] = prime[j];//标记 i*prime[j] 的最小质因数是prime[j]}}
}

版本二

• a[i] i 为质数则为0，否则为 1
• prime[j] 与上面相同

#define MAXN 1000000
int prime[MAXN],v[MAXN];
int m=0;//m表示现在筛出m个质数
void primes()
{for(int i=2;i<MAXN;i++){if(v[i]==0)//如果v[i]为0，说明 i 之前没有被筛到过，i 为质数prime[++m] = i;for(int j = 1;j<=m;j++)//遍历小于 i 的所有质数{//乘起来大于MAXN就跳出循环if(prime[j] > MAXN/i) break;v[i*prime[j]] = 1;//标记 i*prime[j] 的最小质因数是prime[j]//当遇到最小的质数是i的因数时，breakif(i%prime[j]==0)break;}}
}