python中判断素数的函数

来看这一种判断素数（质数）的函数：

form math import sart

def is_prime(n):

if n==1:

return False

for i in range(2, int(sqrt(n) + 1)):

	if n % i == 0:

	return False

return True

看起来，这是一种比较优秀的方法了，因为通过sqrt()函数减少了开方级的计算量。

再来看：

def is_prime(number):

    if number > 1:

        if number == 2:

            return True

        if number % 2 == 0:

            return False

        for current in range(3, int(math.sqrt(number) + 1), 2):

            if number % current == 0:

                return False

        return True

    return False

咋一看，这一次的代码看起来更多。但是，计算量却又在原来的基础上又几乎减少一半。高明之处就在这一句：if number % 2 == 0:，其实这一句就一部将2以及所有合数因子给排除掉了，所以在这一句range(3, int(math.sqrt(number) + 1), 2)中，直接从3起步，步长为2.在range()函数产生的序列是[3,5,7,9,...],比原来由range(2, int(sqrt(n) + 1))产生的[2,3,4,5,6,...]少了合数的部分。

巴特西

python中判断素数的函数

最新文章

热门文章