《专业资料 用筛选法求素数.docx》由会员分享,可在线阅读,更多相关《专业资料 用筛选法求素数.docx(3页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、用筛选法求素数1 .解释下什么是筛选法?筛选法又称筛法,具体做法是:先把N个自然数按次序排列起 来。1不是质数,也不是合数,要划去。第二个数2是质数留下 来,而把2后面所有能被2整除的数都划去。2后面第一个没划去 的数是3,把3留下,再把3后面所有能被3整除的数都划去。3后 面第一个没划去的数是5,把5留下,再把5后面所有能被5整除 的数都划去。这样一直做下去,就会把不超过N的全部合数都筛 掉,留下的就是不超过N的全部质数。2 .程序步骤:1先将1挖掉(因为1不是素数)。用2去除它后面的各个数,把能被2整除的数挖掉,即把2 的倍数挖掉。3用3去除它后面的各数,把3的倍数挖掉。4分别用5各数作为
2、除数去除这些数以后的各数。3具体应用(求100以内的素数):基本思想是:把从1开始的、某一范围内的正整数从小到大顺 序排列,把不是素数的数全部赋值为0,最后只输出不是零的数即 素数。1不是素数,首先把它换为0。剩下的数中选择最小的数是素 数,然后把它的倍数全部换为0。依次类推,直到结束。如有:123456789 10 11 12 13 14 15 16 17 18 19 2021 22 23 24 25 26 27 28 29 301不是素数,换为0。剩下的数中2最小,是素数,然后把它的倍数全部换为0 ,余下的数是:023050709011 0 13 0 15 0 17 0 19 021 0
3、23 0 25 0 27 0 29 0剩下的数中3最小,是素数,然后把它的倍数全部换为0 ,如此下去直到所有的数都被筛完,求出的素数为:2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 974.代码如下(vc6. 0):用筛选法求100以内的素数5. Sint iJk=0,a100 for(i=0;iV100;i+9. Mai=i+l; 将 1100 赋值给 a0a99IL I!12. |13.14.a0=0;for(i=0;iV99;i+先把a0赋值为01516. for(j=i+l;j100;i+17.18.20.aj=0;把不是素数的都赋|值为026 .日27. |28.printf。筛选法求出100以内的素数为:n);29.30. E31. 选出值不为0的数,即素数printf(”4d,aprintf(rT);printf(“n);0)41. |42. |输出10个数后换行|44.0return 0;5 .运行效果:筛选法求出1以内的素数为:2357 1113 17 19 23 293137 4143 47 53 59 6167 7173 Press79 83 89 97any key to continue(全文完)