线性筛

线性筛

一、原理分析

       用筛法求素数的基本思想是：

二、C语言代码

       标记0-100以内的素数

//线性筛 N = M * P
#include <stdio.h>
#define MAX_N 100

int prime[MAX_N + 5];
void init(){
    //第一层循环枚举M
    for(int i = 2; i <= MAX_N; i++){
        if(!prime[i]) prime[++prime[0]] = i;
        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) break;
        }
    }
    return ;
}


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


    return 0;
}

CSDN博客讲解