내일은 알고리즘

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

에라토스테네스의 체에 대한 지식이 있다면 쉽게 풀리는 문제입니다.

우리가 찾아야 하는것은 넓은 범위의 소수입니다. 즉, 천만개의 숫자에 대해 일일히 소수를 판정하지 않고, 소수가 아닌 수를 지워가면 됩니다.

2부터 n까지 숫자를 탐색하면서 이전에 나누어지지 않았다면, 즉 소수라면 answer를 1 더해주고 소수의 배수들을 전부 체크해줍니다. (어떤 소수의 배수라면 소수가 아닙니다. 소수는 1과 자신으로만 나누어진다는 명제의 대우입니다.)

n까지 모두 순회한다면 우리가 목표로 하는 소수의 갯수를 알 수 있습니다.

def solution(n):
    answer = 0
    divided = [False for i in range(n+1)]

    for i in range(2, n + 1):
        if not divided[i]:
            answer += 1
            d = i * 2
            while d <= n:
                divided[d] = True
                d += i

    return answer