这个素数查找算法的复杂度是多少？

Question

我爸爸和我正在尝试确定我爸爸小时候想出的这个素数查找函数的算法复杂性。

第一个循环显然是n，因为它建立了字典。棘手的部分是嵌套循环。外循环运行 n/4 次：0 to n/2, step=2。只有当数字被认为是质数时，内部循环才会运行，这种情况在开始时经常发生，但随着数字的增加，发生的次数越来越少。

def primesV2(n):
    count = 0 # count is for counting the number of iterations done

    # set all even numbers (and 1) to False, else assume prime
    x = {}
    for i in range(n):
        if (i != 2 and i % 2 == 0) or i==1:
            x[i] = False
        else:
            x[i] = True

    # start at 3 because its the first odd prime
    i=3
    while i < n/2: # loop until halfway to n
        if x[i]: # if the number is considered prime
            for j in range(3*i,n,i*2): # if i=3, j will be 9,15,21 (odd multiples of 3)
                x[j] = False # these are not prime
                count = count + 1
        else:
            count = count + 1
        i = i+2

    return x, count

Answer 1

你这里有一个修改过的埃拉托色尼筛法。如果没有任何优化，复杂度将是 O(n log log n)。查看 this wikipedia 文章为什么会这样。

您的优化使它的总速度提高了 4 倍。您最多只能达到 n/2（您可以停在 sqrt n）并且您跳过了一半的倍数。虽然这将使代码更快，但复杂性保持不变（忽略常数因素）。所以它仍然是 O(n log log n).

这个素数查找算法的复杂度是多少？

What is the complexity of this Prime finding algorithm?

python

algorithm

complexity-theory

primes

time-complexity