专业资料 用筛选法求素数.docx
《专业资料 用筛选法求素数.docx》由会员分享,可在线阅读,更多相关《专业资料 用筛选法求素数.docx(3页珍藏版)》请在第一文库网上搜索。
1、用筛选法求素数1 .解释下什么是筛选法?筛选法又称筛法,具体做法是:先把N个自然数按次序排列起来。1不是质数,也不是合数,要划去。第二个数2是质数留下来,而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3,把3留下,再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5,把5留下,再把5后面所有能被5整除的数都划去。这样一直做下去,就会把不超过N的全部合数都筛掉,留下的就是不超过N的全部质数。2 .程序步骤:先将1挖掉(因为1不是素数)。用2去除它后面的各个数,把能被2整除的数挖掉,即把2的倍数挖掉。用3去除它后面的各数,把3的倍数挖掉。分别用5各数作为除数去除这些数以后的
2、各数。3.具体应用(求IOO以内的素数):基本思想是:把从1开始的、某一范围内的正整数从小到大顺序排列,把不是素数的数全部赋值为0,最后只输出不是零的数即素数。1不是素数,首先把它换为0。剩下的数中选择最小的数是素数,然后把它的倍数全部换为0。依次类推,直到结束。如有:1234567891011121314151617181920212223242526272829301不是素数,换为Oe剩下的数中2最小,是素数,然后把它的倍数全部换为0,余下的数是:0230507090110130150170190210230250270290剩下的数中3最小,是素数,然后把它的倍数全部换为0,如此下去直到
3、所有的数都被筛完,求出的素数为:23571113171923293137414347535961677173798389974 .代码如下(vc6.0):二1hiCd1().h:#inc1udeMIiai=i+1;将1100赋值给a0a99a0=0;for(j=i+1;jV100;j+)|18if(a川!=0&a川!=O192022232426,27,29值为0if(a1%ai1=0)aj=;把不是素数的都赋if(ai!=O)选出值不为0的数,即索娄33.35.36.39.40.A42.if(k%10=0)printf(,输出10个数后换行return0;|5 .运行效果:筛选法求出以内的素数为:2357111317192329313741434753596167717379838997Pressanykeytocontinue.(全文完)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 专业资料 用筛选法求素数 专业 资料 筛选 素数