关于筛素数的三种方法

62 阅读 0 评论 41 点赞

我是靠谱客的博主无辜大神，最近开发中收集的这篇文章主要介绍关于筛素数的三种方法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1.最朴素的筛法O(nlogn)

void get_primes2(){
for(int i=2;i<=n;i++){
if(!st[i])
primes[cnt++]=i;//把素数存起来
for(int j=i;j<=n;j+=i)
{	//不管是合数还是质数，都用来筛掉后面它的倍数
st[j]=true;
}
}
}

2.埃氏筛法O(nloglogn)

void get_primes1(){
for(int i=2;i<=n;i++){
if(!st[i])
{
primes[cnt++]=i;
for(int j=i;j<=n;j+=i)
st[j]=true;//可以用质数就把所有的合数都筛掉；
}
}
}

3.线性筛法O(n)

void get_primes(int n)
{
for(int i = 2;i <= n;i++)
{
if(!st[i]) primes[cnt++] = i;
for(int j = 0;primes[j] * i <= n;j++)//筛选小于n的合数
{
st[primes[j] * i] = true;//用最小质因子去筛选合数
//重点：判断如果primes[j]是i的最小质因子，就应该退出循环
//防止重复
if(i % primes[j] == 0)
break;
}
}
}