难度: Easy
原题连接
内容描述
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.
思路 1 - 时间复杂度: O(N * lglgN)- 空间复杂度: O(N)******
线性筛法求素数,但是MLE了
class LinearSievePrimes():
def __init__(self, n): # 求n以内的所有素数(包括n在内)
self.n = n
self.isPrime = [True] * (n+1) # 先将所有数看做素数,然后开始筛选
self.primes = [0] * (n+1) # 所有的素数按从小到大排列
self.prime_cnt = 0 # 素数的个数, 初始化没有素数
def calPrimes(self):
for i in range(2, self.n+1): # 遍历筛去所有最大因数是i的合数
if self.isPrime[i]: # 如果i是素数,把它记录下来
self.primes[self.prime_cnt] = i
self.prime_cnt += 1
j = 0
# 遍历已知素数表中比i的最小素因数小的素数,并筛去合数
while j < self.prime_cnt and self.primes[j] * i <= self.n:
self.isPrime[self.primes[j] * i] = False
if i % self.primes[j] == 0: # 此时self.primes[j]就是i的最小素因数
break
j += 1
class Solution(object):
def countPrimes(self, n):
"""
:type n: int
:rtype: int
"""
lsp = LinearSievePrimes(n-1)
lsp.calPrimes()
return lsp.prime_cnt
思路 2 - 时间复杂度: O(N * lglgN)- 空间复杂度: O(N)******
这个题的hint是已经把算法喂到嘴边了
https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
Input: an integer n > 1
Let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.
for i = 2, 3, 4, ..., not exceeding √n:
if A[i] is true:
for j = i^2, i^2+i, i^2+2*i, i^2+3i, ..., not exceeding n :
A[j] := false
Output: all i such that A[i] is true.
beats 70.58%
class Solution(object):
def countPrimes(self, n):
"""
:type n: int
:rtype: int
"""
isPrime = [True] * n
i = 2
while i * i < n:
if isPrime[i]:
j = i * i
while j < n:
isPrime[j] = 0
j += i
i += 1
return sum(isPrime[2:])
可以写的更 pythonic 一点,beats 84.69%
class Solution(object):
def countPrimes(self, n):
"""
:type n: int
:rtype: int
"""
if n < 3:
return 0
primes = [True] * n
for i in range(2, int(n ** 0.5) + 1):
if primes[i]:
primes[i * i: n: i] = [False] * len(primes[i * i: n: i])
return sum(primes[2:])