筛选法求解素数问题C语言实现

野性酷女 2022-04-23 13:48 195阅读 0赞

**效率提升的算法基础为：**  
1.一个素数的任意整数倍必为非素数；  
2.任何一个合数n一定有一个不超过sqrt(n)的素因子；  
3.在第二轮非素数筛选时，因为是从所有奇数中按从小到大的顺序筛选素数的，由归纳法不难得知：  
若i = 3为素数，则因为在第一轮筛序中已经将2的倍数的数排除了，故可直接从j = 3 \* 3开始进行非素数的筛选；  
若i = 5为素数，则因为在前边的筛选中已将2 \* 5、3 \* 5这两种情况排除，故可直接从j = 5 \* 5开始进行非素数的筛选；  
依次类推。。。  
故第二轮的循环变量j的初始值可置为i \* i；  
因为若一个整数m为奇数，则m \* m + m为一个偶数，而偶数在第一轮筛选中已经被排除。故增量可设为2 \* i。  
**附注：**  
由筛选函数screen\_prime\_number()可知该函数的时间复杂度(不包括素数的打印)为O(n \* sqrt(n))。

/*---------------------------------
    功能：求解区间[1, n]之内的所有素数
    输入示例：
    100
    输出示例：
    2 3 5 7 11
    13 17 19 23 29
    31 37 41 43 47
    53 59 61 67 71
    73 79 83 89 97
    Author: Zhang Kaizhou
    Date: 2019-3-13 16:29:34
    ----------------------------------*/
    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    #define MAXSIZE 100000000 // 最大可求的(2, 100000000)之间的所有素数
    
    int flag[MAXSIZE]; // 标记数组，用所存数据来标记与其下标对应的数字是否为素数
    void screen_prime_number(int n);
    
    int main(){
        int n;
        scanf("%d", &n);
        screen_prime_number(n);
    
        return 0;
    }
    
    void screen_prime_number(int n){ // 筛选法输出1~n之间的所有素数
        int i, j, count = 0;
        for(i = 0; i <= n; i++){ // 因为2为素数，所以所有2的倍数均为非素数
            if(i % 2 == 0){
                flag[i] = 0;
            }else{ // 所有奇数暂时先标记为素数
                flag[i] = 1;
            }
        }
        flag[2] = 1; // 2为素数
        for(i = 3; i < sqrt(n); i += 2){ // 从所有奇数中筛选出素数，从除2外最小的素数3开始
            if(flag[i] == 1){ // 若当前值为素数，则其任意整数倍均为非素数
                for(j = i * i; j < n; j += 2 * i){ // 由奇数分布规律可知，j采取此种初值以及增量效率较高
                    flag[j] = 0;
                }
            }
        }
        for(i = 2; i <= n; i++){
            if(flag[i] == 1){
                printf("%d ", i);
                count++;
                if(count % 5 == 0){
                    printf("\n");
                }
            }
        }
        return;
    }