筛选法求素数

发布于 2018-12-05  551 次阅读


用筛法求素数的基本思想是:把从1开始的、某一范围内的正整数从小到大顺序排列, 1不是素数,首先把它筛掉。剩下的数中选择最小的数是素数,然后去掉它的倍数。依次类推,直到筛子为空时结束。
如有:
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
1不是素数,去掉。剩下的数中2最小,是素数,去掉2的倍数,余下的数是:
3 5 7 9 11 13 15 17 19 21 23 25 27 29
剩下的数中3最小,是素数,去掉3的倍数,如此下去直到所有的数都被筛完,求出的素数为:
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

筛选法可谓是最容易理解的一种寻找素数的方法了

首先举个栗子来解释什么叫做筛选法,了解了解筛选法的思路:

我要寻找从1到15里的素数  (红色代表被筛选掉,不是素数)
第1步:1是素数我不用管,不需要筛选掉1的倍数

1   2   3   4   5   6   7   8   9  10   11   12   13   14   15

第2步:2没有被前面的筛选掉,所以2是素数,然后筛选掉2的倍数 4 6 8 10 12 14

1   2   3   4   5   6   7   8   9  10   11   12   13   14   15

第3步:3没有被前面的筛选掉,那么3是素数,然后筛选掉3的倍数 6 9 12 15

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15

第4步:4被前面的筛选掉了,不是素数,所以跳过此步骤

第5步:5没有被前面的筛选掉,那么5是素数,然后筛选掉5的倍数 10 15

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15

第6步:6被前面的筛选了,不是素数,所以跳过此步骤

第7步:7没有被前面的筛选掉,那么7是素数,然后筛选掉7的倍数 14

1   2   3   4    5    6   7   8  9   10   11   12    13    14   15
第8步:8被前面的筛选了,不是素数,所以跳过此步骤

第9步:9被前面的筛选了,不是素数,所以跳过此步骤

第10步:10被前面的筛选了,不是素数,所以跳过此步骤

第11步:11没有被前面的筛选掉,那么11是素数,然后筛选掉11的倍数,11的倍数大于15了,没得筛选

第12步:12被前面的筛选了,不是素数,所以跳过此步骤

第13步:13没有被前面的筛选掉,那么13是素数,然后筛选掉13的倍数,13的倍数大于15了,没得筛选

第14步:14被前面的筛选了,不是素数,所以跳过此步骤

第15步:15被前面的筛选了,不是素数,所以跳过此步骤

所以筛选后的结果中,谁是素数显而易见了.

1   2   3   4    5    6   7   8  9   10   11   12    13    14   15
素数是 1    2    3    5    7   11    13

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;

int a[1000];

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        a[i] = i+1;
    a[0] = 0;//将a[0]赋值为零,1不是素数
    for(int i=0;i<n-1;i++)   //遍历一遍数组
    {
        for(int j = i+1;j<n;j++)//遍历当前位置之前的所有数据
        {
            if(a[i]!=0&&a[j]!=0)//如果该值已经赋值为零,则不进行运算
            {
                if(a[j]%a[i] == 0)   //j为i的整数倍
                {
                    a[j] = 0;     //将不是素数的都赋值为0
                }
            }
        }
    }
    for(int k=0;k<n;k++)
    {
        if(a[k]!=0)
        {
            cout<<a[k]<<" ";
        }
    }
    return 0;
}

 


像烟花也是过一生,像樱花也是一生,只要亮过和盛开不就好了么?