prime筛选法三种

【文件属性】：
文件名称：prime筛选法三种
文件大小：32KB
文件格式：DOC
更新时间：2012-12-08 01:03:27
prime筛选法 第一种：剔除2 3 4 5 6 ... ... 的倍数。 在i从2开始的增一变化过程中，剔除i的倍数即j*i（j是大于等于2的自然数，j的上限是问题规模M） 为了减少重复步骤，可以每当i递增到等于第一个没有被剔除的（素）数时再剔除该数的倍数， 重复上述过程至i到达问题规模m的平方根+1。 需要说明的三个问题： 假设循环到第n个数，如果该数没有被剔除，那么该数不能是前边所有数的倍数，该数更不可能是后边数的倍数，该 数就是素数。 如果该数是合数却没被剔除，那么该数能分解为两个小于该数的数的积的形式，而前边剔除的数包含了所有小于该 数的数之间的积，这是矛盾的。 为什么筛选循环的第一层只循环至问题规模m的平方根+1 因为，对于一个数m，所有大于该数平方根的数的积已经大于该数了，再剔除下去只是多余。 为什么筛选循环的第二层只循环至MAX/i？ 因为此时j*MAX/i就等于MAX，此时需要标记为错误的数已经到了问题的规模即MAX，没有必要在标记比MAX大的值不 是素数，此外用来标记i*j不是素数的数组只有MAX+1的容量，这样做是向不是自己申请的内存空间里写数据，是危 险的。 还有代码演示~~~~~~~