日韩久久久精品,亚洲精品久久久久久久久久久,亚洲欧美一区二区三区国产精品 ,一区二区福利

Python 判斷素數(shù)(質數(shù))的方法講解

系統(tǒng) 2342 0

質數(shù)又稱素數(shù)。指在一個大于1的自然數(shù)中,除了1和此整數(shù)自身外,不能被其他自然數(shù)整除的數(shù)。素數(shù)在數(shù)論中有著很重要的地位。比 1 大但不是素數(shù)的數(shù)稱為合數(shù)。1 和 0 既非素數(shù)也非合數(shù),2 是素數(shù)。

1.判斷是否是素數(shù):

            
              import timeit
from math import sqrt

def isPrimes1(n):
    if n <= 1:
        return False
    for i in range(2, int(sqrt(n) + 1)):
        if n % i == 0:
            return False
    return True

def isPrimes2(n):
    if n > 1:
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        for x in range(3, int(sqrt(n) + 1), 2):
            if n % x == 0:
                return False
        return True
    return False
    
 print(timeit.timeit("isPrimes1(100)", setup="from chapter01 import isPrimes1", number=10000))
 print(timeit.timeit("isPrimes2(100)", setup="from chapter01 import isPrimes2", number=10000))

            
          

判斷執(zhí)行時間:

            
              0.00563765699999999
0.001561703999999997

            
          

后一種方法將除 2 之外的偶數(shù)排除,大大減少了執(zhí)行時間。

2.求 n 以內的素數(shù)

            
              import timeit
from math import sqrt
import copy

def listPrimes1(n):
    """
    初始所有一個n維數(shù)組 res 表示數(shù)都為素數(shù)。
    從3開始將3的奇數(shù)倍標記成False,即不是素數(shù)。
    之后對每一個素數(shù)此行上一步操作
    這里我們不用管偶數(shù)倍,因為我們最后判定時默認所有偶數(shù)不是素數(shù)
    """
    if n < 3:
        if n == 2:
            return [2]
        return None
    res = [True] * n

    for i in range(3, int(n ** 0.5) + 1, 2):
        res[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
    return [2] + [i for i in range(3, n, 2) if res[i]]

def listPrimes2(n):
    '''
    計算n之內的素數(shù)
    :param n:
    :return:
    '''
    if n < 3:
        if n == 2:
            return [2]
        return None

    num_list = [x for x in range(2, n) if x%2 != 0]

    new_list = copy.copy(num_list)
    # new_list = []
    for i in num_list:
        # new_list.append(i)
        for d in range(3, int(sqrt(i)) + 1,2):
            if i%d == 0:
                new_list.remove(i)
                break
    return [2] + new_list

def listPrimes3(n):
    '''
    計算n之內的素數(shù)
    :param n:
    :return:
    '''
    if n < 3:
     if n == 2:
         return [2]
     return None
  
    return [2] + [p for p in range(2, n) if p %2 != 0 and 0 not in [p % d for d in range(2, int(sqrt(p)) + 1)]]

print(timeit.timeit("listPrimes1(100)", setup="from chapter01 import listPrimes1",number=100))
print(timeit.timeit("listPrimes2(100)", setup="from chapter01 import listPrimes2", number=100))
print(timeit.timeit("listPrimes3(100)", setup="from chapter01 import listPrimes3", number=100))

            
          

整理得到三種實現(xiàn)方法,其中第一種方法執(zhí)行時間最短。

            
              0.000947919999999991
0.003774201000000005
0.004751936999999984

            
          

3.求 m 到 n 之間的素數(shù)

            
              def mnPrimes1(m,n):
    if m == 1:
        num_list = [2] + [p for p in range(2, n) if p % 2 != 0 and 0 not in [p % d for d in range(2, int(sqrt(p)) + 1)]]
    if m >= 2:
        num_list = [p for p in range(m, n) if p % 2 != 0 and 0 not in [p % d for d in range(2, int(sqrt(p)) + 1)]]
    return num_list

def mnPrimes2(m,n):
    num_list = [x for x in range(m, n) if x % 2 != 0 and x != 1]

    new_list = copy.copy(num_list)
    for i in num_list:
        for d in range(3, int(sqrt(i)) + 1, 2):
            if i % d == 0:
                new_list.remove(i)
                break
    if m == 2:
        new_list = [2] + new_list
    return new_list

            
          

更多文章、技術交流、商務合作、聯(lián)系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯(lián)系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發(fā)表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 湘潭县| 文山县| 古蔺县| 辽阳县| 沙雅县| 金湖县| 通江县| 滦平县| 普宁市| 武城县| 宁夏| 罗定市| 昌邑市| 西城区| 雅江县| 平阳县| 叶城县| 治县。| 宁晋县| 会昌县| 麻江县| 观塘区| 寿宁县| 乐陵市| 九江市| 册亨县| 方山县| 遵化市| 汾阳市| 拉萨市| 凤冈县| 临邑县| 永年县| 勐海县| 曲阜市| 沂源县| 青河县| 拜泉县| 汽车| 金寨县| 嘉义市|