前情提要
求质数最简单的方法是暴力破解:
def isPrime(n):
if n < 2: # 如果n比2小的话,你判断它干嘛
return False
elif n == 2: # 2是个质数
return True
res = True
for i in range(3 , n):
for j in range(2, n):
if i % j == 0:
res = False
break
return res
但这样做的效率会很低。有没有办法提高效率呢?
筛选法的核心就一句话:质数的整数倍不是质数。例如,2是质数,但4、6、8等都不是质数,因为它们分别是2的2倍、3倍、4倍等等。同理,3是质数,6、9、12、15等也都不是质数了。
那么如何实现呢?
class Solution:
def countPrimes(self, n: int) -> int:
if n <= 2: # 原题目要求是小于n范围内有多少质数?如果小于2的话,那么就没有。
return 0
isPrime = [True for i in range(n)] # 打表。打一个长度为n的表,表示从0到n-1(包括n-1在内)有哪些是质数。一上来默认全是质数
isPrime[0] = isPrime[1] = False # 由于0和1什么都不算,所以上来就给它们置为False
for i in range(2, n): # 从2开始计算
if isPrime[i] is True: # 由于2肯定是质数,所以放心的算吧。这个条件的意思是如果i是质数的话
for j in range(2, (n - 1) // i + 1): # j在2倍到小于n的情况下i的最大倍数的范围
isPrime[i * j] = False # i的倍数全置于False
res = 0 # 返回的结果
for tf in isPrime: # 那么对照筛选出来的正负表
if tf is True: # 每遇到一个True
res += 1 # 返回的结果数加1
return res
网友评论