문제 - 소수 찾기

문제 설명

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

풀이

첫번째 풀이

자연수 2~N 사이의 소수를 판별하기 위해 각 자연수를 1부터 sqrt(N)까지만 나눠보면서 나누어 떨어지는 값이 있는지 확인하는 방식을 통해 풀었지만, 효율성 테스트에서 시간초과로 통과하지 못했다.

효율성을 통과하기 위한 소수에 대한 수학적 지식이 부족한 것 같아, 다른 풀이를 참고했다. 에라토스테네스의 체 방식을 통해 효율성 문제를 해결해보았다.

에라토스테네스의 체

자연수 2~N 사이의 소수를 판별할 때, 모든 원소를 검사하지 않고 특정 수의 배수들은 판별대상에서 제외시켜 나가는 방법이다.

1. 검사하고자 하는 자연수 범위를 배열로 변환한다.
2. 소수인지 아닌지를 구분하기 위해, 배열의 각 원소는 우선 1로 초기화 한다. (소수가 아니라면 후에 0으로 변환될 것)
3. 배열의 인덱스는 곧 검사하고자 하는 자연수를 의미한다. 배열의 인덱스를 하나씩 돌면서 해당 인덱스의 배수들은 0으로 변환한다. (소수가 아님을 나타냄)
4. 배열에는 소수를 의미하는 1만 남기고, 해당 배열의 원소 개수를 return 한다.