素数筛选算法

Posted on | Post modified:
Words count in article: 311 | Reading time ≈ 1

任务

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

说明

数组valid[i]是否为素数。初始所有的valid[i]为true。从2开始从小到大开始枚举i，若valid[i] = true,则把从i^2开始的每一个i的倍数的valid赋为false。结束之后valid[i] = true的就是素数。

接口

  • void getPrime(int n, int &tot, int ans[maxn])
  • 复杂度：　O(NlogN),O(N)　　两种实现
  • 输入：　　N　　　　　　　　所需素数的范围
  • 输出：
    　　　　　&tot 　　　　　　引用，素数总数　
    　　　　　ans　　　　　　　素数表

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// 素数筛选法 O(NlogN)
#define maxn 1000000

bool valid[maxn];

void getPrime(int n, int &tot,int ans[maxn]) {
  tot = 0;
  int i = 0, j = 0;
  for(i = 2; i < n; ++i) {
    valid[i] = true;
  }
  for(i = 2; i <= n; ++i) {
    if(valid[i]) {
      if(n/i < i) {
        break;
      }
      for(j = i * i; j <= n; j += i) {
        valid[j] = false;
      }
  }
  for(i = 2; i <= n; ++i) {
    if(valid[i]) {
      ans[++tot] = i;
    }
  }
}

// 素数筛选法 O(N)
void getPrime(int n, int &tot, int ans[maxn]) {
  memset(valid, true, sizeof(valid));
  for(int i = 2;i <= n; ++i) {
    if(valid[i]) {
      ++tot;
      ans[tot] = i;
    }
    for(int j = 1; ((j <= tot) && (i * ans[j] <= n)); ++j) {
      valid[i * ans[j]] = false;
      if(i % ans[j] == 0) {
        break;
      }
    }
  }
}

有问题？发送 issues 给我~

0%