보배로움

틀린 부분 또는 더 효율적인 접근법에 대해 피드백 주시면 감사하겠습니다! Programmers 소수찾기 문제 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요. 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.) 입출력 및 예제 제한 조건 n은 2이상 1000000이하의 자연수입니다. 풀이 생각 당연히 모든 수를 다 나눠가며 소수를 구할 순 없다. 제일 직관적으로 해결할 수 있는 에라토스테네스의 체를 사용하자. 방법 모든 수를 소수 집합에 넣어놓자. 낮은 수부터 n까지 순회. 당연히 2를 제외한 짝수는 소수가 아니므로, 제외한다. 각 순회에서 현재 값의 배수가 소수 집합에 존재하면, 그 배수는 소수가 아니므로 집합에서 제거..