204. Count Primes - python3

Count the number of prime numbers less than a non-negative number, n.

My Answer 1: Time Limit Exceeded (17 / 20 test cases passed.)

class Solution:
    def countPrimes(self, n: int) -> int:
        # if n == 0 or n == 1:
        if n in (0,1):
            return 0
        
        count = 0
        isprime = 0
        for i in range(2, n):
            for j in range(2, i):
                if i%j == 0:
                    isprime = 1
                    break
            if isprime == 0:
                count += 1
            isprime = 0
        return count

당연히 비효율적인 코드부터 생각했다...^^
이중 for 문으로 돌리면서 약수가 있으면 무조건 다음 수로 넘어가도록 count

그럼 뭔가 규칙을 찾아야하나본데.. 머리가 안돌아감;

그래서 내가 생각했던 건 n 크기의 prime 리스트를 만들어서 소수면 true 를 아니면 false 를 넣도록 하는 거였는데 너무 메모리 낭비될듯...;

Other Answer 1: (Runtime: 676 ms - 48.47% / Memory Usage: 25.7 MB - 49.76%)

import math
class Solution:
    def countPrimes(self, n: int) -> int:
        if n == 0 or n == 1:
            return 0
        prime = [True]*(n)
        count = 0
        for i in range(2, int(math.sqrt(n))+1):
            if prime[i]:
                j = i*i
                while j < n:
                    prime[j] = False
                    j += i
        for p in range(2, len(prime)):
            if prime[p]:
                count += 1
        return count

결국 베꼈다^^

대부분 2 ~ sqrt(n) 의 범위로 for 문을 돌려서
i 의 제곱에 i 씩 더해가면서 n 보다 작으면 prime 리스트에 false 해줌
(i = 2 -> 4(2^2), 6, 8, ... 는 false)

저런 범위와 계산 방식은 내 머리로는 도저히 생각 못하겠지만..
신기하게도 저렇게 하면 계산이 잘 된다

이대로 외우는 걸로..^^

from primePy import primes
이걸 사용하면 소수 리스트도 구해준다고 함
ex) primes.upto(10) => 2, 3, 5, 7