algorithm - 这个素数搜索算法的复杂性

Question

所以我目前正在学习 Big O 表示法，但我不确定如何计算出我的以下(故意低效)算法的 Big O 是什么:

def getPrimes(n):

primes = [2]    

for i in range(3, n+1):
    remainder = True
    for j in primes:
        if(i % j == 0):
            remainder = False
    if(remainder == True):
        primes.append(i)
return primes

内部 for 循环运行的次数将增加，具体取决于列表“primes”中的项目数量。那么，这对确定 Big O 是什么有何影响(如果有的话)？

Answer 1

检查 Pi(n) function .它的近似值是 n/ln(n)。
总体算法(一种埃拉托色尼筛法实现)复杂度is evaluated as O(n(loglog(n))