그냥 코딩하는 사람의 블로그

- 최대한 효율적으로 구성하고자 에라토스테네스의 체 활용

- 2~n의 제곱근까지의 수에 대하여, 각각의 수들을 2,3,4,5,6,...배 해 나가면서 소수가 아니다.. 라고 체크해주는 방식. 문제에서는 최대 1000000까지 이므로 1000000의 제곱근까지

- 이후 소수의 개수를 구해주면 끝

import math
def solution(n):
    odd = [True] * 1000001
    odd[1] = False
    odd[0] = False
    for i in range(2, int(math.sqrt(1000000))+1):
        if odd[i] == False:
            continue
        for j in range(i*2, 1000001, i): # 배수들 검사
            odd[j] = False

    answer = 0
    for i in range(1, n+1):
        if odd[i] == True:
            answer += 1

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges