寻找质数的算法时间复杂度

Question

我对质数很感兴趣，想知道在比如说1000万这个范围内，找到相对较小的质数最有效的方法是什么。我听说埃拉托斯特尼筛法（SOE）是找小质数最有效的方式。我用Python实现了这个算法，但有几个问题：

1. 我的算法在最坏情况下的运行时间似乎是O(n^2)。我还在学习中，所以我知道这个算法可以更高效。

2. 在寻找质数时，最有效的数学方法和最有效的编程方法有什么区别吗？从数学上讲，SOE是最快的之一，但从编程的角度来看，SOE真的那么快吗？

def FindPrime(n):
    primes = [2, 3]
    for num in range(4, n):
        notprime = False
        for p in primes:
            if num % p == 0:
                notprime = True
        if notprime == False:
            primes.append(num)

    print primes

print FindPrime(100)

Answer 1

1. uʍop ǝpısdn 说得对，你的代码不是最优的素数筛选算法（SOE）

2. 你可以在这里找到我实现的素数筛选算法 这里

   • 这个实现比你的方案更高效

3. 我这个素数筛选算法的复杂度

   • 时间复杂度是 T(0.5·n·DIGAMMA(CEIL(SQRT(n))+0.3511·n)，如果按照代码里的建议使用平方根(N)
   • 当 n=1M 时，时间复杂度是 T(3.80*n)
   • 当 n=10M 时，时间复杂度是 T(4.38*n)
   • 当 n=100M 时，时间复杂度是 T(4.95*n)
   • 当 n=1000M 时，时间复杂度是 T(5.53*n)
   • 所以大致的运行时间是： T((0.3516+0.5756*log10(n))*n)
   • 因此复杂度是 O(n.log(n))

4. 运行速度（运行时间）和复杂度 O() 的区别

   • 实际的运行时间是 t=T(f(n))*c
   • 当 n 足够大时，它会收敛到 t=O(f(n))*c
   • 其中 O() 是算法的时间复杂度
   • 而 T() 是任何 n 的实际运行时间公式（不是 O() !!!）
   • 这里的 c 是处理所有 for 循环的单次处理所需的常数时间等等...
   • 更好的 O() 并不意味着更快的解决方案
   • 对于任何 n，只有在阈值之后
   • O1(f1(n))*c1 < O2(f2(n))*c2
   • 所以如果你能很好地优化 c 常数，那么你可以在某个阈值之前超越更好的复杂度算法
   • 例如你的代码大约是 T(n.n/2) -> O(n^2)
   • 但在小的 n 时可能比我的素数筛选算法 O(n.log(n)) 更快
   • 因为我的算法需要准备表格，这在某个点上会比你的除法花更多时间
   • 但之后你的算法会变得慢得多...

所以对于是否存在最有效的数学和编程解决方案之间的差异

• 答案是 是的，在定义的 N 范围内可能存在差异

Answer 2

首先，你要知道你的算法并不是埃拉托斯特尼筛法，而是试除法。

你的实现可以做一些改进。

1. 使用xrange()，它在内存使用上是O(1)，而range()是O(n)。

2. 在查找时跳过偶数：可以用xrange(4, n, 2)，这样每次跳2个数。

3. 当p > sqrt(n)时，不要测试一个质数p是否能整除n，这是不可能的。

正如你所预测的，这些改动不会影响复杂度的级别，但你会看到性能有明显提升。

至于更快的算法，首先实现一个真正的埃拉托斯特尼筛法，然后再尝试更快的阿特金筛法。