关于找质数用python算法求解？

jamesapple321

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

"""
        find prime number
"""

import math

def is_prime(n):
        """
                判断一个数是否是质数
        """
        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

请问这个i的范围为什么这样写range(2,int(math.sqrt(n)+1) )而不是直接写从2到200之类的，
在请问这个n的值是怎么得来的？

Linux_manne

例子上这样写 是为了提升 运算效率, 找质数 不需要对开根号后面的数做运算..

icymirror

回复 1# jamesapple321
这个是针对求质数的几个优化步骤之一。
之所以求sqrt(n)，是因为一个数的因数是成对出现，而成对出现的时候，上限正好是这个数的平方根。

另外，对于当前算法，如果要进一步减小运算量，可以把range(2, int(math.sqrt(n)+1))进一步分解成：
2和range(3, int(math.sqrt(n)+1), 2) 来减少需要做的运算的量。