[Python] #204. Count Primes(easy)

문제 :

이 문제는 n미만의 숫자들에서 소수를 찾는 문제이다.

처음에 시도한 방법은 2중 for문을 이용해 각 수의 배수의 값의 값을 채워 넣는다.

class Solution:
    def countPrimes(self, n: int) -> int:
        if n <=2 :
            return 0
        prime = [0] * (n+1)
        cnt = 0
        for i in range(2,n):
            if prime[i] == 0 :
                cnt += 1
                for j in range(i,n,i):
                    prime[j] += 1
        
        
        return cnt

결과 

생각보다 속도가 느린 것 같다....

그래서 다른 방법을 생각했는데ㅜㅜ 생각이 안 나서 다른 유저의 답변을 찾았다. 

class Solution:
    def countPrimes(self, n: int) -> int:
        if n <=2 :
            return 0
        prime = [1] * (n)
        prime[0] = 0
        prime[1] = 0
        
        for i in range(2,n):
            if prime[i]:
                prime[i+i:n:i] = [0] * len(prime[i+i:n:i])
        return sum(prime)

이 방법을 사용하게 될 경우

for문을 한 번만 사용해서 문제를 해결 가능하다. 

원리는 인덱싱을 이용한 방법이다. prime 변수에 [1]을 n개 생성한다. 

prime [i+i:n:i]의 indexing을 하게 되면 i*2부터 n까지 i의 간격으로 indexing을 하게 된다. 그리고 그 값에 [0]을 채워 넣는다.

결과