[파이썬] 소수 찾기

문제 설명

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

제한 조건

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

나의 코드

내 알고리즘은 다음과 같다.
1. 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 찾아야 하므로, for문을 사용하여 i 에 숫자를 한개씩 받아온다.
2. 1부터 $\sqrt{i}$ 까지 for문을 이용해 j 에 한개씩 받아온다.
3. i 를 j 로 나눈 나머지가 0인 경우에, j가 1이 아니면 소수가 아니라고 판단하여 변수 count에 1을 더한다.
4. 소수의 개수는 ($n - count - 1)$ 로 계산한다.

문제점

주어진 테스트케이스 두개는 모두 통과했지만, 채점을 해보았을 때 고작 하나밖에 맞히지 못했다.
어느 부분에서 잘못되었는지 좀 더 찾아봐야겠다.

정답

정답이 너무 알고싶어 구글링을 해보았다.
시간초과를 내지 않고 정확하게 풀 수 있는 방법은 '에라토스테네스의 체'라는 알고리즘을 사용하는 것이었다.


에라토스테네스의 체에 대해서는 아래 링크에 정리해놓았다.
[에라토스테네스의 체 알고리즘]

코드

결과

[2, 3, 5, 7, 11, 13, 17, 19]