c语言学习3(线性筛)

1.线性筛

欧拉计划第7题

10001st prime

c语言学习3(线性筛) c语言学习3(线性筛)

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?

c语言学习3(线性筛)



#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;
}

c语言学习3(线性筛)

#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]及之后的给后面的数去筛。这种方法能保证每个数只被筛一遍,又能保证每个数都被筛到。

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

c语言学习3(线性筛)

从图上我们看到,第一列筛掉的是最小素因子是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;
}
 

 

上一篇:偶数是两个素数的和


下一篇:函数在端点处为零的端点效应