标签：11 25 13 23 冬训 素数 序列 周报

埃氏筛选法

概念

埃拉托斯特尼筛法，简称埃氏筛或爱氏筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。

步骤

1. 列出2以后的所有序列：
• 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
2. 标出序列中的第一个素数，也就是2，序列变成：
• 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
3. 将剩下序列中，划掉2的倍数，序列变成：
• 2 3 5 7 9 11 13 15 17 19 21 23 25
4. 如果这个序列中最大数小于最后一个标出的素数的平方，那么剩下的序列中所有的数都是素数，否则回到第二步。
5. 本例中，因为25大于2的平方，我们返回第二步：
6. 剩下的序列中第一个素数是3，将主序列中3的倍数划掉，主序列变成：
• 2 3 5 7 11 13 17 19 23 25
7. 我们得到的素数有：2，3
8. 25仍然大于3的平方，所以我们还要返回第二步：
9. 序列中第一个素数是5，同样将序列中5的倍数划掉，主序列成了：
• 2 3 5 7 11 13 17 19 23
10. 我们得到的素数有：2，3，5 。
11. 因为23小于5的平方，跳出循环.

结论：2到25之间的素数是：2 3 5 7 11 13 17 19 23。

C++代码实现

#include <stdio.h>
#include <math.h>
bool is_prime[1000];
int main(){
    int n;
    scanf("%d", &n);
    for(int i = 0; i <= n; i++){
        is_prime[i] = true;                    //初始化所有的数为素数
    }
    for(int i = 2; i <= sqrt(n); i++){         //从第一个素数2开始筛选
        if(is_prime[i]){                       //如果是素数
            for(int j = i*i; j <= n; j += i){  //则剔除掉它的倍数
                is_prime[j] = false;
            }
        }
    }
    for(int i = 2; i <= n; i++){
         if(is_prime[i]){
             printf("%d\n", i);
         }
    }
    return 0;
}

 

标签：11,25,13,23,冬训,素数,序列,周报
From： https://www.cnblogs.com/Gwzhizi/p/17038969.html