[프래그래머스] 소수 찾기(Python)

문제 설명

1부터 입력받은 숫자 n 사아에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

첫 코드

def solution(n):
    temp = []
    for sosu in range(1, n+1):
        g = []   
        for i in range(1, sosu+1):
            if sosu % i == 0:
                g.append(1)
        if sum(g) == 2:
            temp.append(1)
    answer = sum(temp)
    return answer

정답은 잘 도출해냈지만, 시간 복잡도 측면에서 굉장히 좋지 못한 알고리즘이었다.

에라토스테네스의  체를 사용하여 효율성 높은 알고리즘으로 다시 짜보았다.

개선된 코드

import math
def solution(n):
    array = [True for i in range(n+1)]

    for i in range(2, int(math.sqrt(n))+1):
        if array[i] == True:
            j = 2
            while i * j <=n:
                array[i * j] = False
                j += 1
    return len([i for i in range(2, n+1) if array[i] == True])

핵심 아이디어

여기서 math.sqrt(n)은 n의 가운데 약수를 의미한다. 가운데 약수를 넘지 않는 한도에서 i를 증가시킨다.