打印素数的几种方法及其优化

╰半夏微凉° 2022-05-17 02:17 218阅读 0赞

题目：打印从第n个素数到第m个素数之间的素数（每十个换行）

##### 1. 试除法（傻瓜法） #####

所谓试除法，就是从头到尾一个一个判断是不是素数，并且在判断素数时，从2一直试除到n-1

#define MAX 10000
        #include <stdio.h>
    
        void prime_number(int arr[])
        {
            int ret = 0;
            int j = 0;
            for (int i = 2; i < 10000; i++)
            {
                for (j = 2; j < i; j++)
                {
                    if (i % j == 0)
                    {
                        break;
                    }
                }
                if (j == i)
                {
                    arr[ret] = i;
                    ret++;
                }
            }
        }
    
        int main()
        {
            int n = 0;
            int m = 0;
            int count = 0;
            int arr[MAX] = { 0 };
            scanf("%d%d", &n, &m);
            prime_number(arr);
            for (int i = n - 1; i < m; i++)
            {
                count++;
                printf("%d ", arr[i]);
                if (count % 10 == 0)
                {
                    printf("\n");
                }
                if (i == m - 1)
                {
                    printf("\n");
                }
            }
            system("pause");
            return 0;
        }

###### 优化一: ######

但是我们发现，实际上在判断素数 (i) 的时候，只需要从2到 i / 2即可，再往后就会判断重复。工作量会减少一半

void prime_number(int arr[])
        {
            int ret = 0;
            int j = 0;
            for (int i = 2; i < 10000; i++)
            {
                for (j = 2; j <= i / 2; j++) //修改部分
                {
                    if (i % j == 0)
                    {
                        break;
                    }
                }
                if (j == (i / 2 + 1)) //修改部分
                {
                    arr[ret] = i;
                    ret++;
                }
            }
        }

###### 优化二： ######

我们知道一个数的因数是成对出现的，那么我们只需要判断其中一个即可（判断小的因数），并且小的因数一定小于等于√i（i = a \* b）

void prime_number(int arr[])
        {
            int ret = 0;
            int j = 0;
            for (int i = 2; i < 10000; i++)
            {
                for (j = 2; j <= sqrt(i); j++)
                {
                    if (i % j == 0)//修改部分
                    {
                        break;
                    }
                }
                if (j > sqrt(i)) //修改部分
                {
                    arr[ret] = i;
                    ret++;
                }
            }
        }

###### 优化三： ######

我们知道，素数一定不可能是偶数（除了2），我们我们在判断的时候，就可以直接跳过偶数，只判断奇数

void prime_number(int arr[])
        {
            int ret = 0;
            int j = 0;
            arr[ret] = 2; //修改部分
            for (int i = 3; i < 10000; i += 2) //修改部分
            {
                for (j = 3; j <= sqrt(i); j += 2) //修改部分
                {
                    if (i % j == 0)
                    {
                        break;
                    }
                }
                if (j > sqrt(i))
                {
                    ret++;
                    arr[ret] = i;
                }
            }
        }

##### 2.普通筛选法—— 埃拉托斯特尼筛法 #####

要得到自然数n以内的全部素数，必须把不大于 的所有素数的倍数剔除，剩下的就是素数。  
给出要筛数值的范围n，找出以内的素数。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个质数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个质数5筛，把5留下，把5的倍数剔除掉；不断重复下去……。

实现方法：建立两个数组check和arr，arr数组用来存放素数，check是标记数组，也就是当该数是某个素数的倍数，则标记为1，否则标记为0，  
第一趟：将2标记为0，2的倍数全部标记为1  
第二趟：将3标记为0，3的倍数全部标记为1  
……  
最后，标记为0的即是素数

void prime_number(int arr[])
        { int check[MAX] = { 0 };
            int ret = 0;
            int j = 0;
            for (int i = 2; i < 10000; i++)
            { if (check[i] == 0) { arr[ret] = i; ret++; }
                for (j = i + i; j < 10000; j += i)
                { check[j] = 1; }
            }
        }

##### 3. 线性筛选法——欧拉筛法 #####

在上面的方法中，比如我们判断6是不是素数，2的倍数时需要判断一次，3的倍数时又需要判断一次。所以欧拉筛法通过标记部分保证每个合数只会被它的最小质因数筛去。比如6只会被2的倍数筛掉。

#define MAX 10000
        #define MAXL 100000
        #include <stdio.h>
        #include <math.h>
    
        void prime_number(int arr[])
        {
            int check[MAXL] = { 0 };
            int ret = 0;
            int j = 0;
            for (int i = 2; i < 10000; i++)
            {
                if (check[i] == 0)
                {
                    arr[ret] = i;
                    ret++;
                }
                for (j = 0; j < ret; j++)//修改部分
                {
                    if (i * arr[j] > MAXL) //数字过大退出
                        break;
                    check[i * arr[j]] = 1; 
                    if (i % arr[j] == 0)  //修改部分
                    {
                        break;
                    }
                }
            }
        }

![这里写图片描述][70]

[70]: /images/20220517/65c8558aed144e798ac88fb7327f9791.png