關(guān)于找質(zhì)數(shù)用python算法求解？

jamesapple321

程序如下：
#!/usr/bin/env python
# coding=utf-8

"""
        find prime number
"""

import math

def is_prime(n):
        """
                判斷一個(gè)數(shù)是否是質(zhì)數(shù)
        """
        if n <= 1:
                return False
        for i in range(2,int(math.sqrt(n)+1) ):
                if n % i == 0:
                        return False
        return True
if __name__ == "__main__":
        primes = [ i for i in range(2,100) if is_prime(i)]
        print primes

請(qǐng)問(wèn)這個(gè)i的范圍為什么這樣寫range(2,int(math.sqrt(n)+1) )而不是直接寫從2到200之類的，
在請(qǐng)問(wèn)這個(gè)n的值是怎么得來(lái)的？

Linux_manne

例子上這樣寫 是為了提升 運(yùn)算效率, 找質(zhì)數(shù) 不需要對(duì)開(kāi)根號(hào)后面的數(shù)做運(yùn)算..

icymirror

回復(fù) 1# jamesapple321
這個(gè)是針對(duì)求質(zhì)數(shù)的幾個(gè)優(yōu)化步驟之一。
之所以求sqrt(n)，是因?yàn)橐粋�(gè)數(shù)的因數(shù)是成對(duì)出現(xiàn)，而成對(duì)出現(xiàn)的時(shí)候，上限正好是這個(gè)數(shù)的平方根。

另外，對(duì)于當(dāng)前算法，如果要進(jìn)一步減小運(yùn)算量，可以把range(2, int(math.sqrt(n)+1))進(jìn)一步分解成：
2和range(3, int(math.sqrt(n)+1), 2) 來(lái)減少需要做的運(yùn)算的量。