我的素数测试的时间复杂度是多少？

Question

我对如何计算时间复杂度有基本的了解，但由于素数的随机性，我不确定在这种情况下如何计算它。

快速解释 --> 本质上，我保留了一个运行余数计数，以便我知道下一个素数是什么时候。

我的代码：

import math

n = int(input("Enter the number:\t"))

primeList = []
checkList = []

number = 3
isPrime = True
while number <= math.sqrt(n) and isPrime:

    isChanged = False
    for i, checkNum in enumerate(checkList):
        if checkNum == 1:
            isChanged = True
            checkList[i] = primeList[i]
        else:
            checkList[i] = checkNum - 1

    if not isChanged:

        primeList.append(number)
        checkList.append(number)

        if n % number == 0:
            isPrime = False

    number += 2

if isPrime:
    print("Prime")
else:
    print("Not Prime")

Answer 1

你的算法好像是O(n/log(n))

有sqrt(n)次通过外循环。内循环以小于 sqrt(n) 的素数个数为界。通过 Prime Number Theorem 这是由 sqrt(n)/log(sqrt(n)) 渐近给出的。根据对数定律，这相当于 sqrt(n)/(0.5*log(n)) = 2*sqrt(n)/log(n)。因此，整体复杂度为

O(sqrt(n)*2*sqrt(n)/log(n)) = O(2*n/log(n)) = O(n/log(n))

不用说，这不是检查 n 是否为素数的非常有效的方法。它渐近地比 O(n) 对所有小于 n 的数字的可整除性的天真检查好一点。

我的素数测试的时间复杂度是多少？

What's the Time Complexity of my Primality Test?

python

algorithm

time-complexity

primality-test