本文主要是介绍ccsu 1079求解素数 筛选法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
筛选法求素数
当数据量比较大时候，判素数的方法是会超时的，我们将前面的那道例题改造一下，变成下面这个题目：
桐桐的思考
桐桐在学完了上节课的知识后，对信息学越发感兴趣了。桐桐是一个很善于思考的学生，她发现上节课中例题的n最大是40000，如果数据再大一些，比如n=106，那么判素数的算法能否在1秒内给出答案呢？桐桐用程序实际测试的时间超过了1秒，你能帮助可爱的桐桐解决这个难题吗？即：在1秒的时间内输出不大于n（1＜N≤106）的所有素数。
【输入样例】
10
【输出样例】
2 3 5 7
我们用一个数组a来标识素数的情况（0是，1不是），首先将大于1且不大于n的所有数都标识为素数。举一个例子，n=9时，初始化为：
|
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 数组a | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
从2开始判断，2是素数，因此2的倍数（倍数>1）肯定不是素数，将其筛去：
|
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 数组a | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
接着是3，3没有被2的倍数筛去，因此3是素数，将3的倍数（倍数>1）筛去：
|
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 数组a | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |
接着是4，4是2的倍数已被筛去，4的2倍也是2的4倍数已被筛去，4的3倍已超过9不必考虑。
接着是5，5没有被前面的数筛去，即说明5不能被2~4的数整除，因此5是素数，5的2倍是10，已经超过9不必考虑。
接着是6，6是2的3倍已被筛去，6的倍数与前类同。
接着是7，7没有被前面的数筛去，说明7是素数，7的倍数与前类同。
接着是8，8是2的4倍已被筛去，8的倍数与前类同。
接着是9，9是3的倍数已被筛去，9的倍数与前类同。
现在有一个问题：难道要枚举到9才结束吗？这样的话效率依然没有提高。大家可以发现上述例子中，枚举到4（包括4）以后便没有新的数被筛去，为什么？我们来看4的时候，此时4的2倍已经在考虑2的倍数时筛去，4的3倍便超过了9，这是因为9的平方根是3，任意两个不同的数（>=3）相乘肯定会大于9。因此，在考虑5，6，7，8，9时，他们的倍数（倍数>1）均超过了n的最大值9，不必考虑；他们自身如果没有被前面的数筛去，即是素数，否则不是。
所以，对于输入的n来说，本算法只需要枚举到n的平方根，即可将不大于n的所有素数标识出来。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
int a[1000000];
bool find(int x)
{for(int i=2;i<sqrt(x);i++)if(x%2 !=0)return false;return true;
}
int main()
{int tmp;int n;while(scanf("%d",&n)){if(n == 0)break;memset(a,0,sizeof(a));for(int i=2;i<=sqrt(n);i++){if(a[i] == 0&&find(a[i])){int j=i;tmp=2;while(j<=n){j=i*tmp;a[j] = 1;tmp++;}}}for(int i=2;i<=n;i++){if(a[i]==0)printf("%d ",i);}printf("\n");}return 0;
}
这篇关于ccsu 1079求解素数 筛选法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
