埃拉托色尼筛选法

《埃拉托色尼筛选法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、埃拉托色尼筛选法2015-11-24目录埃拉托色尼筛选法...................................................................................................1素数..........................................................................................................................3分解成素数.........

2、.....................................................................................................3素数表......................................................................................................................4素数素数p有绝好的性质，除了两个朴素的因子1和p，没有其他因子。更不会与其他数一起产生

3、公因子：p与m的可能性说明可能性Ⅰp是m的因子：m=pk可能性ⅡP与m互素：sp+tm=1如果p是ab的因子，下面4种可能中一定不会是第Ⅳ种：p与a、b的可能说明可能ⅠP是a的因子，但不是b的可能ⅡP不是a的因子，但是b的可能ⅢP是a的因子，也是b的可能ⅣP不是a的因子，也不是b的因子如果是第Ⅳ种，那么：s’p+t’a=1且s”p+t”a=1把上面两个式左右相乘得：sp+tab=1这样p和ab互素与p是ab的因子矛盾。分解成素数假如要分解m成素数，就要用比它小的数一个一个测试：……就不用测试了，因为会小于成了左侧某个测试过的值因

4、此从2测试到就可以了，一旦：m=pn只需要对n测试……比如m=17015：17015=5×3403之后从5开始测试就可以了3403=41×8383本身也是素数17015=5×41×83素数表先罗列出“所有”整数。篇幅有限，只罗列到113：把含2的全去掉：下一次，含3的全去掉：下一次，含5的全去掉：下一次，含7的全去掉：到此为止，上表已经没有包含2、3、4、5、6、7、8、9、10等成分的任何数了，只能包含11及以上的成分的数，最小就是121=11×11。言外之意121以下的素数全部被筛选出来了。上面的方法就是：埃拉托色尼筛选法，

5、它可以用来构造素数表而不需要太多计算。如果感兴趣可以加群：495438656