문제
1부터 n 사이에 있는 소수의 개수를 구하기
https://school.programmers.co.kr/learn/courses/30/lessons/12921
성공한 풀이
에라토스테네스의 체
두 번의 실패를 겪고, 결국 구글링으로 힌트를 얻었다.
'에라토스테네스의 체'
위키백과를 참조하여 하나씩 구현해본다.
1. 2부터 n까지 모든 수의 배열
<script>
const arr = [...Array(n-1).keys()].map(v => v+2);
</script>2. 자신을 제외한 배수를 모두 제거
<script>
for (let i = 2; i < Math.sqrt(n); i++) {
if (arr[i-2] !== null) {
for (let j = 2; i * j <= n; j++) {
arr[i * j - 2] = null;
}
}
}
</script>3. 소수 개수 출력!
<script>
return arr.filter(v => v !== null).length;
</script>실패한 풀이
2부터 자신 전까지 나누어 떨어지는지 확인
- for 중첩 반복문과 if문 활용
<script>
function solution(n) {
let cnt = 0;
for (let i = 2; i <= n; i++) {
for (let j = 2; j <= i; j++) {
if (j === i) cnt++;
if (i % j === 0) break;
}
}
return cnt;
}
</script>1은 소수가 아니므로 2부터 n까지 반복문을 돌렸다.
중첩 반복문으로 나누는 수가 자신과 같아지면 cnt++를 수행하고,
1과 자신 외의 숫자로 나누어 떨어지면 멈춘다.
정확성 테스트 10~12, 효율성 테스트를 시간 초과로 실패했다.
2부터 제곱근까지 나누어 떨어지는지 확인
<script>
function solution(n) {
let cnt = 0;
for (let i = 2; i <= n; i++) {
cnt++;
for (let j = 2; j <= Math.sqrt(i); j++) {
if (i % j === 0) {
cnt--;
break;
}
}
}
return cnt;
}
</script>어떤 수 X를 구하는 식은, "X / 약수 = 또 다른 약수" 다.
1 × 20
2 × 10
4 × 5
(제곤급 × 제곱근) (이 경우, 정수는 아니지만 이해를 위해 적었다)
5 × 4
10 × 2
20 × 1
따라서 제곱근까지의 정수를 나누었다.
시간이 개선되어 정확성 테스트에 통과했으나,
효율성 테스트에서 하나 빼고 모두 시간 초과했다.
