目录
题目
- 输入n,返回[2,n)中素数的个数
暴力
- 从2开始到n,一个一个判断是不是素数,是的话就计数器加1。判断素数函数:从2开始到n,判断有没有是n的倍数,有倍数就不是素数
def countPrimes(n:int):
count=0
for i in range(2,n):
if (isPrimes(i)):
count+=1
return count
def isPrimes(n:int):
for i in range(2,n):
if n%i==0:#如果这个数从2开始到自己都没有一个是倍数,则是素数
return False
return True
if __name__ == "__main__":
n=int(input())
print(countPrimes(n))
- 时间复杂度o(n^2)
优化
- 判断素数函数中for循环范围改变了,因为:比如n=12,我们只需要判断26,不需要判断62,中间是以根号n分开的,所以我们判断素数时,只需要判断[2,根号n)
import math
def countPrimes(n:int):
count=0
for i in range(2,n):
if (isPrimes1(i)):
count+=1
return count
def isPrimes1(n:int):
for i in range(2,int(math.sqrt(n))+1):
if n%i==0:#如果这个数从2开始到自己都没有一个是倍数,则是素数
return False
return True
if __name__ == "__main__":
n=int(input())
print(countPrimes(n))
- 时间复杂度o(sqrt(n))
埃拉托斯特尼素数筛选法
- 先初始化数组全为True,然后把是素数的倍数全部删去,最后统计数组中是True的个数返回
import math
def countPrimes1(n: int) -> int:
isPrime = [True for i in range(n)] # 初始化数组为全 True,表示所有数都是质数
for i in range(2, int(math.sqrt(n)) + 1):#乘法因子的对称性
if isPrime[i]:#是素数的情况下,把他的倍数全部删去
for j in range(i*i, n, i):#从i*i开始,到n以i为步长,都是i的倍数,全置为False
isPrime[j] = False
count = 0
for i in range(2, n):
if isPrime[i]:#统计isPrime数组中是ture的个数
count += 1
return count
if __name__ == "__main__":
n=int(input())
print(countPrimes1(n))
- 时间复杂度o(NloglogN)