线性筛法求素数
int primes[N], cnt; // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) primes[cnt ++ ] = i;
for (int j = 0; primes[j] <= n / i; j ++ ) // primes[j] <= n / i === primes[j] * i < n
{
st[primes[j] * i] = true; // primes里面的素数,一定比当前的 i 小,我们是用 素数筛其他数。i是素数则i的倍数一定不是素数,此时他的倍数是用比他小的素数充当的素数
if (i % primes[j] == 0) break; // 当if条件成立是,此时primes[j] 一定是i 的最小因子,每个数只会筛一次,所以是线性的。
}
}
}
作者:yxc
链接:https://www.acwing.com/blog/content/406/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。