素数筛

数论 1 Minute

问题

给定一个正整数N，求出[2,N]内的所有质数。

埃氏筛(the Sieve of Eratosthenes)

原理

显然，所有的合数都至少有一个素因子。
从2开始，从小到大扫描每个数x，并标记它的倍数：
    未被标记的数，显然它不能被[2,x-1]内的任何数整除，这个数是质数，把它的倍数2x,3x,\cdots,\lfloor \frac{N}{x} \rfloor x标记为合数。
    被标记的合数跳过。
对于合数n<p^2，显然n存在一个比p更小的素因子，于是我们在标记p的倍数时候，只需要从p倍开始。

复杂度

对[2,N]内的每个素数p，我们都需要标记\lfloor \frac{N}{p} \rfloor次，而[2,N]内的素数倒数和约为\ln \ln N，所以埃氏筛的复杂度为O(\sum_{p \leq N}\frac{N}{p})=O(N\log \log N)。

代码

#include<bits/stdc++.h>
using namespace std;

const int MAXN=(int)1e7+10;

bool v[MAXN];
//[2,n],0->prime,1->not prime
int prime[MAXN];
//prime[0]->the number of all primes of [2,n]
//prime[i]->the ith prime number of [2,n]
void EratoSieve(int n);

int main()
{
  int n=(int)1e7;
  EratoSieve(n);
  cout<<prime[0]<<endl;
}

void EratoSieve(int n)
{
  int m=0;
  for (int i=2;i<=n;i++) {
    if (v[i]==0) {
      prime[++m]=i;
      for (int j=i;j<=n/i;j++) {
      //be care for overflow
        v[i*j]=1;
      }
    }
  }
  prime[0]=m;
}

欧拉筛(the Sieve of Euler)

代码

#include<bits/stdc++.h>
using namespace std;

const int MAXN=(int)1e7+10;

bool v[MAXN];
//0->prime,1->not prime
int prime[MAXN];
//prime[0]->the number of all primes of [2,n]
//prime[i]->the ith prime number of [2,n]
void EulerSieve(int n);

int main()
{
  int n=(int)1e7;
  EulerSieve(n);
  cout<<prime[0]<<endl;
  return 0;
}

void EulerSieve(int n)
{
  int m=0;
  for (int i=2;i<=n;i++) {
    if (v[i]==0) {
      prime[++m]=i;
    }
    for (int j=1;j<=m && prime[j]<=n/i;j++) {
      v[i*prime[j]]=1;
      if (i%prime[j]==0) break;
    }
  }
  prime[0]=m;
}
未知 的头像

发布者：风竹曦

已发布

留下评论