(프로그래머스 연습 문제 풀이) 소수 찾기

문제 설명
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.(1은 소수가 아닙니다.)

제한 조건
n은 2이상 1000000이하의 자연수입니다.

입출력 예
n               result
10                4
5                  3

입출력 예 설명
입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환
입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

def solution(n):
    answer = 0
    # 에라토스테네스의 체
    array = [True] * (n + 1)
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if array[i] == True:
            for j in range(i + i, n + 1, i):
                array[j] = False
                
    for i in range(2, n + 1):
        if array[i] == True:
            answer += 1
    return answer

에라토스테네스의 체를 사용하여 풀어보았다. 이는 완전탐색 방식인데, 2의 배수를 모두 지우고, 3의 배수를 모두 지우고, 5의 배수를 모두 지우면서 소수를 찾는 것이다. 기존의 배열에서 True로 통일하고, 이후 배수에 해당하는 부분들은 False로 바꿔주면서 결국 True 개수를 반환하면 된다.