LeetCode. Count Primes [Math]

Problem:

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.

 

-Summary-

Used Sieve of Eratosthenes

 

1. List all the numbers start from the 2.

2. 2 is a Prime number.

3. Remove all the number that is multiple of 2.

4. The smallest number that is not removed, is a 3 which is a prime number as well.

5. Remove all the number that is multiple of 3.

6. The smallest number that is not removed, is a 5 which is a prime number as well.

7. Remove all the number that is multiple of 5.

8. Keep doing until the square root of n. 

(if n is not a prime number, n = a * b. Either a or b should be less than the √n. if both bigger than √n, then a*b is bigger than n.)

ex) if n = 24, All the divisor will be 2,3,4[less √24] than 6,8,12 [bigger than √24]

 

Sieve of Eratosthenes process

Time Complexity: O(n*log(log n)) --> Sum of reciprocals of all numbers up to n, which is O(n log n): Harmonic number

- proper upper-bound is n(1/2 + 1/3 + 1/5 + 1/7 + …), that is the sum of reciprocals of primes up to n, which is O(n log log n)

 

Space Complexity: O(√n)

 

처음엔 brute force로밖에 생각이 안나서 discussion과 힌트의 도움을 받아 이런 알고리즘이 있다는걸 배우게 되었다.+

오늘도 새로운 알고리즘을 배우고 간다.

 

https://brilliant.org/wiki/sieve-of-eratosthenes/

Sieve of Eratosthenes | Brilliant Math & Science Wiki

모든 문제에 대한 저작권은 LeetCode 회사에 있습니다. [Copyright © 2020 LeetCode]