(HDUACM2010版-09)筛选法及预处理.ppt

《(HDUACM2010版-09)筛选法及预处理.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2021/8/241第二讲筛选法及预处理（附-菜鸟的21个经典错误）2021/8/242例1-素数判断题目描述：给定一个N（1intmain(){inti,n;while(scanf("%d",&n)==1){for(i=2;i

2、21/8/244朴素算法优化版本#include#includeintmain(){inti,n,x;while(scanf("%d",&n)==1){x=(int)sqrt(n);for(i=2;i<=x;i++)if(n%i==0)break;if(i>x)printf("YES");elseprintf("NO");}}2021/8/245例2-求所有素数题目描述：给定一个N（1

3、题目特点：不是求一个素数，而是求一段素数（一种常见的情况就是求指定范围的所有的素数）如果还用常规求素数方法，可能的问题是？2021/8/247筛选法求素数基本思想：素数的倍数一定不是素数实现方法：用一个长度为N+1的数组保存信息（0表示素数，1表示非素数），先假设所有的数都是素数（初始化为0），从第一个素数2开始，把2的倍数都标记为非素数（置为1），一直到大于N；然后进行下一趟，找到2后面的下一个素数3，进行同样的处理，直到最后，数组中依然为0的数即为素数。说明：整数1特殊处理即可。2021/8/248效果演示000000000000000000015432671110981

4、213171615142021/8/249效果演示000100000000000000015432671110981213171615142021/8/2410效果演示000100100000000000015432671110981213171615142021/8/2411效果演示000100100001000000015432671110981213171615142021/8/2412效果演示000100100101100101015432671110981213171615142021/8/2413效果演示000100100111100111015432671110

5、981213171615142021/8/2414效果演示000100100111100111015432671110981213171615142021/8/2415效果演示000100100111100111015432671110981213171615142021/8/2416效果演示000100100111100111015432671110981213171615142021/8/2417参考代码（筛选法）#include#includeinta[100001];intmain(){inti,j,n;while(scanf("%d

6、",&n)==1){for(i=2;i<=n;i++){if(a[i]==0)for(j=i+i;j<=n;j+=i)a[j]=1;}printf("2");for(i=3;i<=n;i++)if(a[i]==0)printf("%d",i);printf("");}return0;}2021/8/2418例3-求素数个数题目描述：给定一个N（1#incl

7、udeinta[100001];intmain(){inti,j,n,count;while(scanf("%d",&n)==1){count=0;for(i=2;i<=n;i++){if(a[i]==0)for(j=i+i;j<=n;j+=i)a[j]=1;}for(i=2;i<=n;i++)if(a[i]==0)count++;printf("%d",count);}return0;}2021/8/2420题目分析(1)题目特点：数据量超大！分析：前面算法的瓶颈：每组数据都求素数