Description
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.
Solutions
题意就是找比 $n$ 小的质数的个数了,所谓质数就是除了 1 和其本身不能被其他整除的数。
1. Brute Force
想先快速实现一个暴力的版本,结果超时了:
class Solution:
def countPrimes(self, n: int) -> int:
if n <= 1:
return 0
count = 0
for i in range(1, n):
if self.isPrimes(i):
count += 1
return count
def isPrimes(self, num):
if num <= 1:
return False
for i in range(2, int(num ** 0.5) + 1):
if num % i == 0:
return False
return True
2. 埃拉托斯特尼筛法
埃拉托斯特尼筛法就是用来解决这个问题,以此从小到大找到所有质数的倍数给全部删掉即可。
# Time: O(nloglogn)
# Space: O(n)
class Solution:
def countPrimes(self, n: int) -> int:
if n <= 2:
return 0
tags = [True for _ in range(n)]
tags[0], tags[1] = False, False
sqrtn = int(round(n ** 0.5))
for i in range(2, sqrtn + 1):
if tags[i]:
for j in range(i * i, n, i):
tags[j] = False
return sum(tags)
# 20/20 cases passed (500 ms)
# Your runtime beats 63.22 % of python3 submissions
# Your memory usage beats 62.07 % of python3 submissions (27.6 MB)
牛人优化之后的版本更快:
class Solution(object):
def countPrimes(self, n):
"""
:type n: int
:rtype: int
"""
if n <= 2:
return 0
s = [True] * n
s[0] = s[1] = False
sqrtn = int(round(n**0.5))
for i in xrange(2, sqrtn + 1):
if s[i]:
s[i*i: n: i] = [False] * len(xrange(i*i, n, i))
return s.count(True)
# Runtime: 132 ms, faster than 98.74% of Python online submissions for Count Primes.
# Memory Usage: 34.9 MB, less than 76.32% of Python online submissions for Count Primes.