문제 설명

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를 반환

접근 방법

첫 시도에는 1부터 n사이에 주어진 수들을 순회하며 i를 2부터 int(sqrt(i))까지 나눠보며 나눠 떨어지는 경우가 있을 경우에는 카운팅하지 않는 방법으로 코드를 작성하였다. 테스트 케이스와 정확도 테스트 모두 통과했지만 효율성에서 통과하지 못하는 케이스가 발생했다.

그래서 에라토스테네스의 체를 이용하기로 했다. 찾아본 결과 에라토스테네스의 체를 이용하여 소수를 구하는 방법이 가장 빠르다고 한다. 에라토스테네스의 체의 원리는 다음과 같다.

• 소수를 체크하는 배열 chk를 만든다.
• 2부터 n까지 순회하며 만약 chk[i]가 소수 체크가 되어있지 않을 경우 chk에서 i의 배수를 인덱스로 갖는 원소들을 모두 소수가 아니라고 체크한다. (소수의 배수는 소수가 아니므로)
• chk배열에서 소수라고 체크되어 있는 갯수를 출력한다.

이와 같은 방식을 이용하여 코드를 구현하였다.

• 소수 판별 체크를 위한 배열 chk를 False*(n+1)로 선언한다.
• 2부터 n까지 순회하는 i에 대한 for문을 돌린다.
  -> 만약 chk[i]가 False일 경우,
  --> 임시 변수 idx를 선언하고 i*2를 넣어준다.
  --> idx가 n보다 작거나 같을 동안 반복하는 while문을 돌린다.
  ---> chk[idx]를 True로 갱신해준다.
  ---> idx를 i만큼 증가시킨다.
• 정답을 저장할 변수 answer를 선언하고 chk의 False개수-2를 저장한다. (-2를 하는 이유는 chk에 0, 1도 False로 저장되어 있기 때문이다. 0, 1은 소수가 아니다.)
• answer를 반환한다.

solution.py

def solution(n):
    chk=[False]*(n+1)
    for i in range(2, n+1):
        if not chk[i]:
            idx=i*2
            while idx<=n:
                chk[idx]=True
                idx+=i
    answer=chk.count(False)-2
    return answer