gpt4 book ai didi

python - 我的素数测试的时间复杂度是多少?

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:35:13 26 4
gpt4 key购买 nike

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

快速解释 --> 本质上,我正在对余数进行连续计数,以便知道下一个素数何时出现。

我的代码:

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")

最佳答案

你的算法似乎是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 的数字的整除性的天真检查好一点。

关于python - 我的素数测试的时间复杂度是多少?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/51632183/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com