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

1.判斷是否是素數：

            
              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))

            
          

判斷執行時間：

            
              0.00563765699999999
0.001561703999999997

            
          

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

2.求 n 以內的素數

            
              import timeit
from math import sqrt
import copy

def listPrimes1(n):
    """
    初始所有一個n維數組 res 表示數都為素數。
    從3開始將3的奇數倍標記成False，即不是素數。
    之后對每一個素數此行上一步操作
    這里我們不用管偶數倍，因為我們最后判定時默認所有偶數不是素數
    """
    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之內的素數
    :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之內的素數
    :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))

            
          

整理得到三種實現方法，其中第一種方法執行時間最短。

            
              0.000947919999999991
0.003774201000000005
0.004751936999999984

            
          

3.求 m 到 n 之間的素數

            
              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