1. What I learned
Sieve of Eratosthenes
Eratosthenes sieve is the fastest way to find the prime numbers. It is to erase the multiples of that number from the smallest number. And the last remaining numbers are the pirme numbers.
2. How I sloved
I had to count the prime number before the input. So I used the sieve of Eratosthenes, and when I checked each number, I only had to check the root value of that number. I marked the unchecked number with one. If the number is not a prime number, it has been changed to zero. And I wrote as below because I didn’t have to check the number smaller than the number I was checking.
eratos[i*i:n:i] = [0] * (1 + (n-1-i*i)//i)
3. Code
class Solution:
def countPrimes(self, n: int) -> int:
if n < 3:
return 0
eratos = [1] * n
eratos[0] = 0
eratos[1] = 0
i = 2
while i*i < n:
if eratos[i] == 1:
eratos[i*i:n:i] = [0] * (1 + (n-1-i*i)//i)
i += 1
return sum(eratos)
4. Result
Runtime : 112 ms(99.05%), Memory usage : 37.2 MB(5.03%)
(Runtime can be different by a system even if it is a same code.)