几个有意思的问题_第二弹

苏小脉

evolniar 发表于 2011-4-11 11:00
你看错啦，我的代码是，通过算一次，不通过也算一次~

while 结束后会立刻进入 if 内部 o_o

苏小脉

evolniar 发表于 2011-4-12 04:40
while (n < number)

    {

while 终止的时候，n >= number

苏小脉

evolniar 发表于 2011-4-12 11:50
我明白你的意思了哈。
还有，我们的代码除了i与i*2，之外，没什么差别。
怎么会“互补”呢？怎么可能减少 ...

学生判断了外层循环变量 i 是否是质数，如果是则往后筛，否则不用筛，因为 i 的质因数的所有倍数在先前的迭代中已经都被筛掉了，其中就包含了 i 自己的所有倍数。

苏小脉

evolniar 发表于 2011-4-12 14:46
你这个想法很好，我也考虑过了。
但是你有没有想过，每判断一次 i 是不是质数，也算一次迭代啊。。。所以 ...

学生前日见先生说“每一次判断都得算作一次迭代”时就颇为疑惑，不解先生对迭代的定义是什么。依 Wikipedia 定义，迭代是“通过从一个初始估计出发寻找一系列近似解来解决问题的过程”。在我们讨论的 Eratosthenes 筛法中，若是不计初始化，只剩枚举奇数和筛选这两个（循环）过程可被称为迭代。我们加入计数递增之处正是（处于相同循环之中的）一系列语句被循环执行了一次之时。

这里是否是质数的判断仅仅涉及到了一次数组的随机访问，O(1) 的时间并不会增加算法复杂度，反而会避免很多次不必要的循环。我们计算迭代次数纯粹是为了满足楼主在主楼的需求，但迭代次数只能针对算法时间复杂度，不能针对真实的执行效率。

苏小脉

evolniar 发表于 2011-4-12 15:32
你的意思是，跳过i=9,15,21,27？
我对迭代(iteration?)的定义是：每进行一次一次判断，即为一次迭代
.

i 是所有合数的时候都跳过了。462 是我的答案，457 是不计没进入内层 while 的场合，但确实该计~