[프로그래머스] 소수 찾기

https://programmers.co.kr/learn/courses/30/lessons/12921

문제 설명

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

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

제한 조건

• n은 2이상 1000000이하의 자연수입니다.

입출력 예

풀이

def solution(n):
    answer = 0
    num_list = [True] * (n + 1)
    num_list[0], num_list[1] = False, False
    
    for i in range(2, n+1):
        if num_list[i] == True:
            j = 2
            while i * j <= n:
                num_list[i * j] = False
                j += 1
    answer = sum(num_list)
    return answer

• 제한 조건에서 n이 크기 때문에 시간복잡도를 고려해야한다.
• 인덱싱을 편하게 하기 위해 $n+1$ 크기를 갖는 리스트를 모두 True로 생성하고, 에라토스테네스의 체를 활용했다.
• 현재 숫자가 소수일 경우 현재 수의 2배, 3배, ... 인 수들은 전부 소수가 아니므로 False로 저장
• while문을 사용해 제한적으로 루프를 돌았기 때문에 효율성 검사까지 통과할 수 있었다.