目录
筛法
所谓筛法是一种思想，就像名字一样，筛去多余的，筛去错误的。多数情况用数组标记，复杂度看起来很大，但代码跑起来确是越跑越快。
素数筛法
问题引入
把n以内素数全找出来(n<=100000)
大家一定想得到第一种方法，暴力，遍历。
//暴力
#include<stdio.h>
#include<math.h>
int isprime(int n)
{
n = sqrt(n);
for(int i = 2; i < n; i++)
{
if(n%i==0)
return 0;
}
return 1;
}
int main()
{
scanf("%d",&n);
for(int i = 1; i <= n; i++)
{
if(isprime(n))
printf("%d ",i);
}
return 0;
}
注：用n=sqrt(n),可以增加运算速度,毕竟sqrt也是很慢的。但是这种方法还是很慢，慢在每次都要判断。
接下来看筛法
代码分析
所谓素数，就是不能表示为比它更小的数的乘积。
且，任何一个素数的倍数一定不是素数。
我们先定义一个数组来存100000以内数是否的素数，下标表示数，数组的值1表示是素数，0表示不是素数。
我们可以换个角度思考，要找素数，其实只要把不是素数的排除就可以了。
接下来我们可以构造一张表。
初始
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
我们可以把2的倍数变成1，因为任何一个素数的倍数一定不是素数。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
然后是3的倍数
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 1 |
。。。。。。
照这样就可以得到一张素数表了，哈哈。
看代码。
//筛选法
#include<stdio.h>
#include<math.h>
int a[100001];
int main()
{
int n;
while(scanf("%d",&n) == 1)
{
for(int i = 2; i <= n; i++)
{
if(a[i] == 0)
{
for(int j = i*2; j < n; j+=i)
a[j] = 1;
}
}
printf("2");
for(int i = 3; i <= n; i++)
{
if(a[i] == 0)
printf(" %d",i);
}
}
reutrn 0;
}
这个代码还可以改进。
第一，我们不用筛到n，其实只要和暴力方法一样，筛到sqrt(n)就可以了。
第二，我们筛3时多筛了3*2，筛5时多筛了5*2,5*3,5*4。只要从i*i开始筛就可以了。
//筛选法优化一
#include<stdio.h>
#include<math.h>
int a[100001];
int main()
{
int n;
while(scanf("%d",&n) == 1)
{
n = sqrt(n);
for(int i = 2; i <= n; i++)
{
if(a[i] == 0)
{
for(int j = i*i; j < n; j+=i)
a[j] = 1;
}
}
printf("2");
for(int i = 3; i <= n; i++)
{
if(a[i] == 0)
printf(" %d",i);
}
}
reutrn 0;
}
其实还可以改进，这里我就不说了。
把2的情况用位运算，再把j+=i变为j+=2*i
总结
看起来时间复杂度为O(n*n)，其实在处理很多数据时，它是越跑越快，相当于O(6*n)。
另外
1，如果要判断素数个数，可以用一个数组存一下有几个，结合筛法，也是很方便的。
2，如果要判断50-100有几个素数，只要（100的素数个数-50的素数个数），再判断一下100与50的素数情况。
3，这种筛法叫埃拉托斯特尼筛法。
下一篇：线性筛法（一）--素数筛法（一）