素数筛

素数筛

一、原理分析

       用筛法求素数的基本思想是:把从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;
}


   转载规则


《素数筛》 赵小亮 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
线性筛 线性筛
线性筛 一、原理分析       用筛法求素数的基本思想是: 二、C语言代码       标记0-100以内的素数 //线性筛 N = M * P #
2020-10-09
下一篇 
TCP网络编程(一) TCP网络编程(一)
TCP网络编程(一) 一、TCP网络编程       TCP 网络编程是目前网络开发中的主要编程方式之一。TCP协议处于网络传输层中,实现了一个应用程序到另外一个应用程序的数据传输,要进行嵌入式网络
  目录