素数筛

素数筛

一、原理分析

       用筛法求素数的基本思想是：把从1开始的、某一范围内的正整数从小到大顺序排列，1不是素数，首先把它筛掉。剩下的数中选择最小的数是素数，然后去掉它的倍数。依次类推，直到筛子为空时结束，如下面的分析：

二、C语言代码

       标记0-100以内的素数

1.普通代码

#include <stdio.h>
#define MAX_N 100
int prime[MAX_N + 5];

void init(){
    for(int i = 2; i <= MAX_N; i++){
        if(prime[i]) continue; //对偶逻辑减少缩进
       for(int j = i * 2; j <= MAX_N; j += i){
            prime[j] = 1;
       }
    }
    return ;
}

int main(){
    init();
    for(int i = 2; i <= MAX_N; i++){
        if(prime[i]) continue;
        printf("%d\n", i);
    }

    return 0;
}

2.优化代码

//优化代码
#include <stdio.h>
#define MAX_N 100
int prime[MAX_N + 5];

void init(){
    for(int i = 2; i <= MAX_N; i++){
        if(prime[i]) continue;
       // for(int j = i * 2; j <= MAX_N; j += i){
       //优化后，时间复杂度为O(n*loglogn)
        for(int j = i * i; j <= MAX_N; j += i){
            prime[j] = 1;
       }
    }
    return ;
}

int main(){
    init();
    for(int i = 2; i <= MAX_N; i++){
        if(prime[i]) continue;
        printf("%d\n", i);
    }

    return 0;
}

3.优化代码

//优化代码
#include <stdio.h>
#define MAX_N 100

int prime[MAX_N + 5];

void init(){
    for(int i = 2; i <= MAX_N; i++){
        if(prime[i]) continue;
        prime[++prime[0]] = i; //用原来的数组存储素数个数以及素数
        for(int j = i * i; j <= MAX_N; j += i){
            prime[j] = 1;
        }
    }
    return ;
}

int main(){
    init();
    for(int i = 1; i <= prime[0]; i++){
       // if(prime[i]) continue;
        printf("%d\n", prime[i]);
    }

    return 0;
}