def is_prime(x):
'''
Function to check if a number is prime
'''
if x == 2:
return True
if x%2 != 0: #Check if number is even since all primes are odd except 2
a = [x % i for i in range(2,x+1)]
b = [i for i in a if i == 0] # Checks to make sure there's only one modulus of 0
if len(b) == 1:
return True
else:
return False
else:
return False
所以,就像是的,请问时间复杂度是多少(所有这些0/n的东西),我如何发现,一个好的资源链接将是有帮助的(:
2
除外,您可以在循环之前专门测试它。这不会改变复杂性,因为它是一个常数,但它将时间减少了一半李>math.sqrt(x)
以下的数字。这将最坏情况复杂性从O(n)更改为O(sqrt(n))李>x % i
的列表。这提高了最佳案例的复杂性李>比检查所有奇数更好的是使用Sieve of Eratosthenes只检查素数
当您从2到
x+1
运行一个循环时,您的复杂性是O(x)
您只需检查
sqrt(x)
。这将把复杂性降低到O(sqrt(x))
。(一旦你找到一个因素,你就可以打破它,即使它不会降低最糟糕的时间复杂度)只要换一行-
a = [x % i for i in range(2,math.sqrt(x+1))]
为什么要求平方根
a = b.c
,那么至少有一个a
的除数小于sqrt(a)
,或者如果a
是平方数a = b*b
,则等于李>有许多快速启发式和概率(Miller-Rabin是非常著名和常用的)算法用于更快的素数检测
这里有一个是确定性的:
Adleman–Pomerance–Rumely素性测试是一种确定数字是否为素数的算法。与其他更有效的算法不同,它避免了使用随机数,因此是一种确定性素性测试
它的复杂性是
log(x)^O(logloglogx)
信用证:https://github.com/wacchoz/APR_CL/blob/master/APR_CL.py
相关问题 更多 >
编程相关推荐