質(zhì)數(shù)又稱(chēng)素?cái)?shù)。指在一個(gè)大于1的自然數(shù)中，除了1和此整數(shù)自身外，不能被其他自然數(shù)整除的數(shù)。素?cái)?shù)在數(shù)論中有著很重要的地位。比 1 大但不是素?cái)?shù)的數(shù)稱(chēng)為合數(shù)。1 和 0 既非素?cái)?shù)也非合數(shù)，2 是素?cái)?shù)。

1.判斷是否是素?cái)?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í)行時(shí)間：

            
              0.00563765699999999
0.001561703999999997

            
          

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

2.求 n 以內(nèi)的素?cái)?shù)

            
              import timeit
from math import sqrt
import copy

def listPrimes1(n):
    """
    初始所有一個(gè)n維數(shù)組 res 表示數(shù)都為素?cái)?shù)。
    從3開(kāi)始將3的奇數(shù)倍標(biāo)記成False，即不是素?cái)?shù)。
    之后對(duì)每一個(gè)素?cái)?shù)此行上一步操作
    這里我們不用管偶數(shù)倍，因?yàn)槲覀冏詈笈卸〞r(shí)默認(rèn)所有偶數(shù)不是素?cái)?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):
    '''
    計(jì)算n之內(nèi)的素?cái)?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):
    '''
    計(jì)算n之內(nèi)的素?cái)?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))

            
          

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

            
              0.000947919999999991
0.003774201000000005
0.004751936999999984

            
          

3.求 m 到 n 之間的素?cái)?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