Symbol
[프로그래머스] LV 1. 소수 찾기 - Javascript
프로그래머스 LV 1. 소수 찾기 - Javascript 문제 풀이 입니다.
2024-03-28

📌문제

문제 설명

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

제한사항

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

입출력 예

nresult
104
53

입출력 예 설명

입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환
입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

📌My Solution


채점 결과

정확성 : 75.0
효율성 : 6.3
합계 : 81.3 / 100.0
for문을 3부터 시작, 소수 판별 for문은 제곱근을 이용하는 등 성능개선을 위해 이것저것 해봤지만 효율성 테스트를 통과하지 못했다.

📌Best Solution


Best Solution은 에라토스테네스의 체Set 을 사용한 방식이다.
우선 2부터 n까지의 모든 자연수를 Set에 추가한 후 가장작은 수 j를 제외한 j의 배수들을 제거하면서 소수를 찾는 방식이다.
어차피 2를 제외한 2의 배수들은 제거 대상이므로 처음부터 Set에 저장하지 않고
자연수의 제곱근 까지만 for문을 돌면서 남아있는 가장 작은 수의 배수들을 제거해 나가면서 효율성 테스트를 통과했다.