如果你需要从1到N生成素数,那么"愚蠢"的方法就是迭代从2到N的所有数字并检查这些数字是否可以被到目前为止找到的任何素数除以小于有问题的数字的平方根.
在我看来,Eratosthenes的筛子做了同样的事情,除了其他方式 - 当它找到一个素数N时,它标记所有N的倍数的数字.
但是,当你找到N时是否标记X,或者你检查X是否可以被N除可,基本的复杂性,大O保持不变.你仍然按照数字对进行一次恒定时间操作.事实上,愚蠢的算法一旦找到一个素数就会中断,但是Eratosthenes的筛子会多次标记每个数字 - 一次对于每个素数它都可以被分割.对于除素数之外的每个数字,这是最少两倍的操作.
我在这里误解了什么吗？