以Python列表特性為切入點(diǎn)的求質(zhì)數(shù)列表的方法

2019-11-14 16:59:00

字體：大中小

供稿：網(wǎng)友

一般，構(gòu)造一個含有2-x之間所有質(zhì)數(shù)的列表，我們采用最簡單的遍歷判斷質(zhì)數(shù)的方法：

 # 方法一
 1 PRime = [] 2  3 def is_prime(n): 4     if n <= 1: 5         return False 6     for i in range(2, int(math.sqrt(n)) + 1): 7         if n % i == 0: 8             return False 9     return True10 11 for i in range(2, x):12     if is_prime(i):13         prime.append(i)

這個方法的優(yōu)勢在于邏輯簡單，易于想到。

而對于Python非常有特色的列表操作，可以用其特性以更少的步驟獲得指定范圍的質(zhì)數(shù)：

# 方法二
prime = [2]def list_prime(n):    if n < 2:        print("invalid input")    for i in range(3, n + 1, 2):        prime.append(i)        k = int(math.sqrt(i))        for x in prime:            if i % x == 0:                prime.remove(i)                break            elif x > k:                break

對比第一種方式中，如果遇到質(zhì)數(shù)x，那么每個它前面的小于sqrt(x)的數(shù)都會與之求余運(yùn)算一次，需要消耗較多的計(jì)算時間；

第二種方式下，在遇到質(zhì)數(shù)x時，僅僅將其與小于sqrt(x)的質(zhì)數(shù)進(jìn)行求余運(yùn)算，可以減少計(jì)算時間。

但，相對于運(yùn)算節(jié)省的時間，第二種方式下用到了prime.remove()方法，而這會占用大量運(yùn)算量，因此進(jìn)行了優(yōu)化：

 # 方法二（改進(jìn)）
 1 prime = [2] 2  3 def list_prime(n): 4     if n < 2: 5         print("invalid input") 6     for i in range(3, n + 1, 2): 7         k = int(math.sqrt(i)) 8         flag = True 9         for x in prime:10             if i % x == 0:11                 flag = False12                 break13             elif x > k:14                 break15         if flag:16             prime.append(i)