1.线性筛

欧拉计划第7题

10001st prime

Problem 7

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

#include <stdio.h>
#define MAX_N 200000
​
int prime[MAX_N + 5] = {0};
void init() {
    for (int i = 0; i < MAX_N; i++) {
        if (prime[i]) continue;
        prime[++prime[0]] = i;
        for (int j = i; j <= MAX_N / i; j++) {
            prime[j * i] = 1;
        }
    }
    return;
}
​
int main() {
    init();
    printf("%d\n", prime[10001]);
    return 0;
}

#include <stdio.h>
#define MAX_N 100
​
int prime[MAX_N + 5] = {0};
​
void init() {
    // i等价于M
    for (int i = 2; i <= MAX_N; i++) {
        if (!prime[i]) prime[++prime[0]] = i;
        // j表示素数表中每一个素数下标
        for (int j = 1; j <= prime[0]; j++) {
            if (prime[j] * i > MAX_N) break;
            // prime[j]等价于P,prime[j] * i等价于N
            prime[prime[j] * i] = 1;
            if (i % prime[j] == 0) break;
        }
    }
}
​
int main() {
    init();
    for (int i = 2; i < prime[0]; i++) {
        printf("%d\n",prime[i]);
    }
    return 0;
}

关键之处在：if(i%prime[j]==0) break;

这句代码保证了每个数最多被筛一次，将时间复杂度降到了线性。

证：prime[]数组中的素数是递增的,当i能整除prime[j]，那么i*prime[j+1]这个合数肯定会被prime[j]乘以某个数筛掉。因此，这里直接break掉，将iprime[j+1]及之后的给后面的数去筛。这种方法能保证每个数只被筛一遍，又能保证每个数都被筛到。

为了更好的理解，画出前面几次筛的情况

从图上我们看到，第一列筛掉的是最小素因子是2的数，第二列筛掉的是最小素因子为3的数，依次类推，可以把所有的合数都筛掉。

因为是按照最小素因子筛选，每个数的最小素因数只有一个，所以可以保证每个数都只会被筛一遍。

例如，i=6 时，第一个素数是2，能整除，筛掉12后就break；至于第二个素数3，6x3中的最小素因数肯定是前一个素数2，所以它要到 i=9，素数取2时才被筛掉。

上面的这种 线性筛法 也称为 Euler 筛法 （欧拉筛法）。

欧拉筛的速度大概是埃氏的3~4倍，然而在小数据中却有被完爆的可能（因为埃氏筛cache友好？）

---

100以内数字因子个数

#include <stdio.h>
#define MAX_N 100
​
int prime[MAX_N + 5] = {0};
int f[MAX_N + 5] = {0};
int cnt[MAX_N + 5] = {0};
​
void init() {
    for (int i = 0; i <= MAX_N; i++) {
        if (!prime[i]) {
            prime[++prime[0]] = i;
            f[i] = 2;
            cnt[i] = 1;
        }
        for (int j = 1; j <= prime[0]; j++) {
            if (prime[j] * i > MAX_N) break;
            prime[prime[j] * i] = 1;
            if (i % prime[j] == 0) {
                f[i * prime[j]] = f[i] / (cnt[i] + 1)*(cnt[i] +2);
                cnt[i * prime[j]] = cnt[j] + 1;
                break;
            }
            else
            {
                f[i * prime[j]] = f[i] * f[prime[j]];
                cnt[i * prime[j]] = 1;
            }
        }
    }
    return;
}
​
int main() {
    init();
    for (int i = 2; i <= MAX_N; i++) {
        printf("f[%d]=%d\n",i,f[i]);
    }
    return 0;
}