pytudes._2021.leetcode.easy._204__count_primes

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

Examples:

>>> Solution().countPrimes(0)
0

Module Contents

Classes

Solution

Functions

count_primes(n)	Returns the number of primes between [2, n)
count_primes_separate_loop_for_2(n)	Returns the number of primes between [2, n)

class pytudes._2021.leetcode.easy._204__count_primes.Solution

countPrimes(n)

Parameters:

n (int) –

Return type:

int

pytudes._2021.leetcode.easy._204__count_primes.count_primes(n)

Returns the number of primes between [2, n)

Complexity:

Time: O(nlog(logn)) Space: (n) (for the boolean array)

• This becomes the bottleneck for large values of n (e.g., ≥ 10^9).

In those cases, a segmented sieve algorithm (either Eratosthenes or Sorenson) or incremental sieve would be more appropriate.

See Also:

• https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Segmented_sieve

Args:

n: the limit to which we are to count primes

Examples:

>>> count_primes(7)
3
>>> count_primes(10)
4
>>> count_primes(0)
0
>>> count_primes(1)
0

Parameters:

n (int) –

Return type:

int

pytudes._2021.leetcode.easy._204__count_primes.count_primes_separate_loop_for_2(n)

Returns the number of primes between [2, n)

Complexity:

Time: O(nlog(logn)) Space: (n) (for the boolean array)

• This becomes the bottleneck for large values of n (e.g., ≥ 10^9).

In those cases, a segmented sieve algorithm (either Eratosthenes or Sorenson) or incremental sieve would be more appropriate.

See Also:

• https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Segmented_sieve

Args:

n: the limit to which we are to count primes

Examples:

>>> count_primes_separate_loop_for_2(7)
3
>>> count_primes_separate_loop_for_2(10)
4
>>> count_primes_separate_loop_for_2(0)
0
>>> count_primes_separate_loop_for_2(1)
0

Parameters:

n (int) –

Return type:

int