亚洲av成人无遮挡网站在线观看,少妇性bbb搡bbb爽爽爽,亚洲av日韩精品久久久久久,兔费看少妇性l交大片免费,无码少妇一区二区三区

Chinaunix

標(biāo)題: 關(guān)于找質(zhì)數(shù)用python算法求解？ [打印本頁]

作者: jamesapple321 時間: 2016-07-17 15:50
標(biāo)題: 關(guān)于找質(zhì)數(shù)用python算法求解？
程序如下：
#!/usr/bin/env python
# coding=utf-8

"""
      find prime number
"""

import math

def is_prime(n):
      """
            判斷一個數(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

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

作者: Linux_manne 時間: 2016-07-18 10:42
例子上這樣寫是為了提升運算效率, 找質(zhì)數(shù) 不需要對開根號后面的數(shù)做運算..

作者: icymirror 時間: 2016-07-18 10:42
回復(fù) 1# jamesapple321
這個是針對求質(zhì)數(shù)的幾個優(yōu)化步驟之一。
之所以求sqrt(n)，是因為一個數(shù)的因數(shù)是成對出現(xiàn)，而成對出現(xiàn)的時候，上限正好是這個數(shù)的平方根。

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

歡迎光臨 Chinaunix (http://www.72891.cn/)