求不大于n的连续质数序列——埃拉托色尼筛选法.docx

埃拉托色尼筛选法 目的：产生一个不大于给定整数n的连续质数序列 该算法一开始初始化一个2-n的连续整数序列，作为候选质数。然后，在算法的第一个循环中，它将2的倍数从序列中消去。然后，它只想列表中的下一个数字3，又将其倍数消去。以这个方法做下去，知道序列中已经没有可消去的元素。 倍数仍未被消去的最大数p应该满足的条件： 如果在当前倍数中，我们正在消去p的倍数，那么第一个值得考虑的倍数是p*p，因为其他更小的倍数2p，……，（p-1）*p已经在先前的步骤中从序列里消去了，显然，p*p不会大于n，p也不会大于√n向下取整的值。 C： //埃拉托色尼筛选法求不大于给定整数n的连续质数序列 #inclu