title: "leetcode-204 Count Primes 質(zhì)數(shù)計(jì)數(shù)"
我的博客 https://zszdata.com/2019/03/09/count-primes/
Count Primes
Count the number of prime numbers less than a non-negative number, n.
Example:
Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.
Solution:
1：
class Solution:
def countPrimes(self, n: int) -> int:
count = 0
for i in range(2,n):
for j in range(2,i):
if i%j == 0:
break
else:
count += 1
return count
This solution could work but time limit exceeded. Complexity of this solution is O(n2).超時(shí)了。
2:
如果一個(gè)數(shù)是合數(shù)檐什，那么它的最小質(zhì)因數(shù)肯定小于等于它的平方根眨业。
因?yàn)槿绻钚≠|(zhì)因數(shù)已經(jīng)大于平方根了，那么大的質(zhì)因數(shù)就要大于平方根峦阁，兩個(gè)質(zhì)因數(shù)相乘肯定大于這個(gè)數(shù)。所以只需要判斷這個(gè)數(shù)是否能被小于其平方根的所有數(shù)整除耘成。
def countPrimes(self, n: int) -> int:
if n <= 2:
return 0
else:
res = 0
for i in range(2, n):
isPrime = 0
for j in range(2, int(i**0.5)+1):
if i%j ==0:
isPrime = 1
if isPrime == 0:
res += 1
return res
還是超時(shí)了榔昔。。
3:
Eratosthenes 埃拉托斯特尼篩法
gif
- 是質(zhì)數(shù)瘪菌，同時(shí)劃去所有2的倍數(shù)撒会，接著查看剩下的數(shù)
- 是質(zhì)數(shù)，同時(shí)劃去所有3的倍數(shù)师妙，接著查看剩下的數(shù)
- 一直進(jìn)行到n的平方根（向上取整）诵肛。
sol2經(jīng)驗(yàn)：只需要判斷小于等于平方根的所有數(shù)
def countPrimes(self, n: int) -> int:
if n <= 2:
return 0
else:
output = [1]*n
output[0],output[1] = 0,0
for i in range(2,int(n**0.5)+1):
if output[i] == 1:
output[i*i:n:i] = [0]*len(output[i*i:n:i])
return sum(output)
pic
pic
