Leetcode # 204. Count Primes

Problem

Counpute len([i for i in range(n) if is_prime(i)])

https://leetcode.com/problems/count-primes

First Solution (Time Limit Exceeded)

質數的定義

1. 屬於自然數 ℕ (大於 0 )
2. 只有兩個正因數 ( 1 和自己)

驗證是否 n 為質數只需要驗證 [2, ⌊n^1/2⌋]

1. 如果 ⌊n^1/2⌋ ∈ ℕ ⇔ n = (n^1/2)²
2. 如果 n = f₁ × f₂; f₁ < f₂; f₁, f₂ ∈ ℕ ⇒ f₁ < n^1/2 < f₂

Time Complexity: O(n * (n ** (1/2)))
Space Complexity: O(n)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def __init__(self):
    self.primes = []
  def is_prime(self, n): # O(n ** (1/2))
    for prime in self.primes:
      if n % prime == 0: return False
    for i in range(self.primes[-1] + 1 if self.primes else 2, isqrt(n) + 1):
      if n % i == 0: return False
    self.primes.append(n)
    return True
  def countPrimes(self, n: int) -> int:
    for n in range(2, n):
      self.is_prime(n)
    return len(self.primes)

Solution: Sieve of Eratosthenes

Time Complexity

Sieve of Eratosthenes 的 time complexity:

$$ O\Bigg(\frac{n}{2} + \frac{n}{3} + \frac{n}{4} + …\Bigg) = O\Bigg(n \cdot \bigg(\frac{1}{2} + \frac{1}{3} + \frac{1}{4} + …\bigg)\Bigg) $$

Ref

• WIKIPEDIA: Divergence of the Sum of the Reciprocals of the Primes

Code

Time Complexity: O(n * log(log(n)))
Space Complexity: O(n)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def countPrimes(self, n: int) -> int:
    numbers = [False] * 2 + [True] * (n - 2)
    // if n is not a prime ⇒ the second largest factor <= sqrt(n) 
    for i in range(isqrt(n) + 1):
      if numbers[i]:
        for j in range(i * 2, n, i):
          numbers[j] = False
    return sum(numbers)

Last Updated on 2023/08/24 by A1go