本文共 1556 字，大约阅读时间需要 5 分钟。

素数筛法与埃氏筛法的实现

1. 简单介绍

素数筛法是一种高效的算法，用于找出一定范围内的素数。它通过事先标记非素数的数字，进而快速筛选出所有的素数。这种方法在数论和密码学领域应用广泛。

2. MaxFactor埃氏筛法

MaxFactor埃氏筛法是一种经典的素数筛法实现，主要思想如下：

bool is_pri[N+5];void prime() {    for (int i = 0; i <= N; i++) {        is_pri[i] = true;    }    is_pri[0] = false;    is_pri[1] = true;    for (int i = 2; i <= N; i++) {        if (is_pri[i]) {            for (int j = 2 * i; j <= N; j += i) {                is_pri[j] = false;            }        }    }}

工作原理

3. MaxFactor线式筛法

MaxFactor线式筛法是一种更高效的素数筛法，通过线性筛法优化了空间复杂度：

int pri[N+10];void prime() {    memset(pri, 0, sizeof(pri));    pri[1] = 0; // 0表示素数    for (int i = 2; i <= N; i++) {        if (!pri[i]) {            for (int j = i * i; j <= N; j += i) {                pri[j] = 1;            }        }    }}

工作原理

4. 普通求法

普通方法通过逐个检查每个数的因数来判断是否为素数：

int m, pri[max];void prime(int n) {    int i, j;    memset(pri, 0, sizeof(pri));    for (i = 2; i <= n; i++) {        for (j = 2; j <= sqrt(i); j++) {            if (i % j == 0) {                break;            }        }        if (j > sqrt(i)) {            pri[m++] = i;        }    }}

工作原理

5. 优化建议

• MaxFactor埃氏筛法和MaxFactor线式筛法在空间复杂度上相比传统方法有显著提升，建议在处理大规模数据时使用。
• 普通求法适用于小范围内的数据，简单易懂，但效率较低。

转载地址：http://jbfe.baihongyu.com/