专业资料 用筛选法求素数.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.（全文完）