素数筛（欧拉筛，线性复杂度）

采用最小质因数法来筛选合数，将其去除。
通过已有的质数，去除以该质数为最小质因数的合数
其余一些解释在代码注释中

//prime用于保存素数，isprime用于记录该数是否为素数，n表示范围上限,prime[0]存储素数个数
void get_prime(int prime[], bool isprime[], int n)
{
int cnt = 0;
memset(isprime, 1, sizeof(bool)*n);
isprime[1] = 0;
for (int i = 2; i <= n; i++)
{
if (isprime[i]) prime[++cnt] = i; //将留下的质数按升序放入prime数组中
for (int j = 1; j <= cnt && i * prime[j] <= n; j++)
{
//通过已有的质数筛选出最小质因数为prime[j]的合数
isprime[i * prime[j]] = 0;
//重要步骤*
//如果i的因子有prime[j],假设i=a*prime[j]那么i可以分成那么在下一步i*prime[j+1]==a*prime[j]*prime[j+1]
//prime[j]<prime[j+1],那么最小质因数将不是prime[j+1],而是prime[j]
//这句话放在后面位置是因为如果一个合数是a*prime[j]*prime[j]的形式，也是符合最小质因数的
if (i % prime[j] == 0) break;
}
prime[0] = cnt;
}
}

最后

以上就是机智墨镜为你收集整理的素数筛（欧拉筛，线性复杂度）的全部内容，希望文章能够帮你解决素数筛（欧拉筛，线性复杂度）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。