为何两种求2000000以下素数和的Python解法性能差异巨大？

这两种解法虽然看起来都是埃拉托斯特尼筛法的思路，但核心实现细节的差异直接导致了性能的天差地别，咱们拆开来说：

第一种解法的性能黑洞 #

• list.remove(d)的毁灭性开销：Python的列表是动态数组，不是链表。当你调用remove(d)时，程序首先要遍历整个列表找到d的位置（这已经是O(n)的时间），然后删除它之后，后面所有元素都得往前挪一位来填补空缺——又是一次O(n)的操作。对于2000000这么大的范围，要删除的非素数数量极多，每次删除的开销都会叠加，直接把运行时间拉到分钟级别。
• d in list的额外拖慢：在删除前还要检查d是否在列表里，这个操作同样是遍历整个列表的O(n)操作，等于每一次删除都要做两次全列表遍历，雪上加霜。

第二种解法的高效秘诀 #

• 用标记代替删除：第二种解法根本没动列表的结构，只是把非素数对应的位置设为0。这个操作是O(1)的——直接通过索引定位到元素修改，不需要移动任何其他元素，开销可以忽略不计。
• 跳过已标记的数：通过temp[x-2]==0判断当前数是否已经被筛掉，直接跳过后续的筛选循环，这是埃氏筛的正确优化，避免了对已经确定为非素数的数做重复处理。
• 稳定的列表结构：整个过程中列表长度不变，遍历和索引访问都是稳定的低开销操作，没有任何额外的结构调整成本。

顺便提一句，第二种解法里temp=list其实是个小细节：Python里列表是引用类型，temp和list指向的是同一个列表，所以修改temp就是修改list，这里不影响结果，但如果想真正复制列表的话，应该用temp = list.copy()或者temp = list[:]，不过这对性能没影响～

内容的提问来源于stack exchange，提问作者Pedro