素数筛法

[micsama]

素数筛法

8

    要求1-100000范围内的素数，用自定义函数挨个求，复杂度为O(n * sqrt(n))，非常耗时。可以用素数筛法来求大范围的素数。

方案一： 用一个标记数组，全部初始化为true，0,1不是素数，直接记为false；从未遍历过的最小的标记为true的位置开始，所有是这个位置的下表的倍数的位置都标记为false。 如：从第一个true，2开始，所有小于100000且是2的倍数的都标记为false； 再从3开始，所有小于100000且是3的倍数的都标记为false；循环到开始位置大于100000，退出函数。

 bool isprime[1010];
 memset(isprime, true, sizeof(isprime));
 for (int i = 2; i <= 1000; i++)
 {
     if (isprime[i])
         for (long long j = 2; j * i <= 1000; j++)
             isprime[j * i] = false;
}

方案二：快速线性素数筛法（欧拉筛法） 筛除合数时，保证每个合数只会被它的最小质因数筛去。因此每个数只会被标记一次，所以算法时间复杂度为O(n)。

bool flag[100001];
memset(flag, 0, sizeof(flag));
vector<int> prime;
int cnt = 0;
for(int i = 2; i <= n; ++i)
{
    if(!flag[i])
    {
        prime.push_back([i]);
        cnt++;
    }
    for(int j = 0; j < cnt; ++j)
    {
        if (i * prime[j] > n)break;
        flag[i * prime[j]] = 1;
        if (i % prime[j] == 0)break;
    }
} 

[UNICKCHENG]

素数筛法

[任务] 给定一个正整数Ｎ，求出［２，Ｎ］中的所有素数 [设计] 将正整数Ｎ中的素数筛选出后存放至数组a中

定义法　（Ｏ（n^1.5））

//zhicheng
bool is_Prime(int n)
{
if(n<=1) return false;
for(int i=2;i<=n/i;i++) if(n%i==0) return false;
return true;
}

埃拉托斯特尼筛法 (O(nloglogn))

//zhicheng
void getPrime1(int n,int& tot,int* a)
{
bool valid[n];
memset(valid,true,sizeof(valid));
for(int i=2;i<=n;i++)
{
if(valid[i]) a[tot++]=i;
for(int j=2*i;j<=n;j+=i) valid[j]=false;
}
}

欧拉筛法 (O(n))

//zhicheng
void getPrime(int n,int& tot,int* a)
{
bool valid[n];
memset(valid,true,sizeof(valid));
for(int i=2;i<=n;i++)
{
if(valid[i])a[tot++]=i;
for(int j=0;j<=tot&&i*a[j]<=n;j++)
{
valid[i*a[j]]=false;
if(i%a[j]==0) break;
}
}
}

参考资料

• 判断一个数是不是素数
• 欧拉函数求法与欧拉筛法求素数