class Solution(object):
def countPrimes(self, n):
"""
:type n: int
:rtype: int
"""
if n < 2 : return 0
primes = [True for _ in range(n)]
primes[0] = primes[1] = False
result = 0
for index, p in enumerate(primes) :
if p == True :
result += 1
i = 1
np = (n - 1) / index
while i < np :
i += 1
new_p = index * i
primes[new_p] = False
return result
문제 풀이
time complexity 줄일 수 있는 방법...