07-22-2025

埃氏筛

高效筛选出某个范围内所有质数 的经典算法

思路：假设我们想找出 2 ~ N 之间的所有质数：

  1. 先假设 2~N 都是质数。

  2. 从 2 开始，把它的所有倍数（2×2, 2×3, 2×4…）都标记为合数。

  3. 再找到下一个未被标记的数（一定是质数），然后把它的所有倍数标记为合数。

  4. 不断重复，直到处理到 √N 为止。

  5. 剩下所有未被标记的数就是质数。

C代码

1
2
3
4
5
6
7
8
9
10
11
// 初始化
    for (int i = 2; i <= n; i++) isPrime[i] = true;

    // 埃氏筛
    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }

从小到大，遇到质数就划掉他的倍数

we gt introduce the vise of eula

compared with vise of esteranis, this vise would’t get any re-count if its not prime, let start

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
C form

#include <stdbool.h>
#include <stdlib.h>

void vise_of_eula(int num){
    if(num < 2){
        obviously, no prime
    }
    bool *is_composite = (bool*) calloc(num+1, sizeof(bool));
    int *Primes = (int*) malloc((num+1) * sizeof(int)),cnt = 0;
    for(int i = 2; i <= num; i++){
        if(!is_composite){
            Primes[cnt++] = i;
        }
        for(int j = 0; j < cn && i * Primes[j] <= num; j++){
            is_composite[i * Primse[j]] = true;
            if(i % Primse[j] == 0) break;
        }

    } 
    free(is_composite);
    int *final_Prime = realloc(Primes, cnt*sizeof(int));
    free(Primes); 
}