要寻找所有< N的素数，我们应该怎么做？Naive的做法是对于所有< N的数字i我们判断i是否是素数，这样时间复杂度为O(N ^ (3/2))。有没有更快的做法呢？
Sieve of Eratosthenes可以让我们在O(N)的时间解决这个问题，同时我们要付出O(N)的空间作为代价。具体的思路为，我们用一个array来表示array[i]是否为素数，默认所有entry设为true，对于所有2 <= i <= N的整数i：
- 如果array[i]为false， continue
- 如果i >=sqrt(N)我们将i加入结果集
- 如果i < sqrt(N)并且array[i]为true，将i加入结果集，并且将所有array[k * i](i <= k, k * i < n)标记为false，表示这个数不是素数，因为他有不等于1和它本身的因子i
这个算法为什么是正确的？对于整数i我们有结论当：我们遍历到i并且array[i]为true，那么i一定是素数，因为：
- 如果i == 2，array[2]默认为true
- 如果array[i]为true，那么代表i没有因子x, where 1<x<i，因为如果x存在，在前面的某次循环i一定会被标为false
代码如下：
几个值得注意的细节：
- 为什么j从i*i开始？因为i*k(k < i)已经被标为false了，例如i = 3，我们不用从6开始，因为6在i = 2的循环已经被标为false了
- 为什么i >=sqrt(N)之后我们就直接加入结果集而不做后续的处理？因为i*i>N超出了我们要考虑的范畴
No comments:
Post a Comment