題目描述

簡而言之就是，找一個.txt文件中質數的個數。
傳送門

解法

# 讀取文本數據
with open('primes.txt', 'r', encoding='utf-8') as f:data = f.read().split()# 將數據分為兩組，一組大于10^8，另一組小于等于10^8
lst1 = [int(i) for i in data if len(i) <= 8]
lst2 = [int(i) for i in data if len(i) > 8]# 使用埃氏篩法找到小于等于10^8的所有質數，如果x是質數，那么大于 x 的 n 的倍數 2x,3x,… 一定不是質數
res = []  # 用于存儲質數
ans = [True for _ in range(10**8+1)]  # 一開始假設所有的數都是質數
for i in range(2, 10**8 + 1):if ans[i]:res.append(i)for j in range(i+i, 10**8 + 1, i):ans[j] = False# 求數組中質數的數量
# lst1中元素較多使用埃氏篩法尋找，lst2中元素較少，直接暴力尋找
count = 0
for i in lst1:if ans[i]:count += 1# 暴力循環尋找質數
flag = True
for i in lst2:for j in range(i+1, int(i**0.5) + 1):if i % j == 0:flag = Falsebreakif flag:count += 1flag = True
print(count)

思路

如果需要判斷的元素較多可以通過建立埃氏篩來求解質數，如果元素數量較少則可以通過暴力求解來判斷一個數是否為質數。

結果

通過

查漏補缺

需要掌握判斷一個數是否為質數的兩種方法：
1、埃氏篩法：如果x是質數，那么大于 x 的 n 的倍數 2x,3x,… 一定不是質數
2、暴力求解法：質數是一種因數只有1和它本身的數。

更新日期

2024.02.23

參考來源

藍橋網