厄拉多塞（The Sieve of Eratosthenes）质数筛选法

程序员文章站 2022-06-08 13:24:22

...

质数：

质数只有两个因数：1和本身

任何大于1的自然数，要么本身是质数，要么可以分解为几个质数之积，且这种分解是唯一的

质数的个数是无限多的，2是最小的质数

厄拉多塞（The Sieve of Eratosthenes）质数筛选法

厄拉多塞筛选法（The Sieve of Eratosthenes）是解决某一范围内的质数个数的常见算法。

算法的关键思想是：

任何大于1的自然数，要么本身是质数，要么可以分解为几个质数之积，且这种分解是唯一的

实现思路：

假设从起始位置开始的所有数都是质数（一般是从2开始，也可以自行指定），从起始位置开始循环向前判断，若为质数，则其倍数都标记为非质数，循环结束条件是上界n，需要提前设定。最后循环结束后，仍然被标记为质数的即为所求，可输出并计数。

优缺点：

实现简单，但是对空间的消耗较大。

//假设求2-200之间的质数
#include<stdio.h>
#include<string.h>
#define n 200
int main()
{
    int flag[n+1];
    memset(flag,1,sizeof(flag));//定义在string.h中
    flag[0] = flag[1] = 0;
    for(int i=2; i<n; ++i)
    {
        if(flag[i]){
            for(int j=2; i*j<n; ++j){//将质数的倍数都置为0
                flag[i*j] = 0;
            }
        }
    }
    int cnt = 0;//记录质数个数
    for(int i=2; i<n; ++i){
        if(flag[i]){
            ++cnt;
            printf("%d ",i);
        }
    }
    printf("\n 质数个数为：\n"，cnt);
    return 0;
}

算法的双层循环处还可以优化以提高执行效率

//假设求2-200之间的质数
#include<stdio.h>
#include<string.h>
#define n 200
int main()
{
    int flag[n+1];
    memset(flag,1,sizeof(flag));//定义在string.h中
    flag[0] = flag[1] = 0;
    for(int i=2; i<sqrt(n); ++i)//外层循环结束条件到sqrt(n)就可以
    {
        if(flag[i]){
            for(int j=i*i; j<n; j+=i){//将质数的倍数都置为0。内层循环从i*i开始即可，之前的已经判断过
                flag[j] = 0;
            }
        }
    }
    int cnt = 0;//记录质数个数
    for(int i=2; i<n; ++i){
        if(flag[i]){
            ++cnt;
            printf("%d ",i);
        }
    }
    printf("\n 质数个数为：\n"，cnt);
    return 0;
}

电科19年计算机复试有考察过厄拉多塞筛选算法，但是实现方式稍有不同，思路是一样的。供大家学习。

厄拉多塞（The Sieve of Eratosthenes）质数筛选法