문제설명
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)
- i! ≤ n
제한사항
- n은 2이상 1000000이하의 자연수입니다.
입출력 예
| n | result |
| 10 | 4 |
| 5 | 3 |
2
입출력 예 설명
- 입출력 예 설명입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환 - 입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환
정답
function solution(num) {
// 숫자 0부터 확인하므로 num에 +1을 꼭해준다.
let array = Array(num + 1).fill(true);
// 0과 1은 소수가 아니니까 false 처리
array[0] = false;
array[1] = false;
// 2부터 num까지 숫자를 1씩 더하면서 확인한다.
for (let i = 2; i * i <= num; i++) {
// num의 i번째 배열이 true이면, (2,3,4,5..쭉 가므로..)
if (array[i]) {
// 그 배열의 제곱, 4, 9, 16, 25 .. 쭉쭊쭉 가서 false 처리 해준다.
for (let j = i * i; j <= num; j += i) {
array[j] = false;
}
}
}
// 모두 false처리를 마치고, array에 담긴 true값을 반환해 그 개수를 확인한다.
return array.filter((a) => a).length;
}
console.log(solution(10));
1) 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
2) 2는 소수이므로 오른쪽에 2를 쓴다.
3) 자기 자신을 제외한 2의 배수를 모두 지운다.
4) 남아있는 수 가운데 3은 소수이므로 오른쪽에 쓴다.
5) 자기 자신을 제외한 3의 배수를 모두 지운다.
6) 남아있는 수 가운데 5는 소수이므로 오른쪽에 쓴다.
7) 자기 자신을 제외한 5의 배수를 모두 지운다.
8) 남아있는 수 가운데 7은 소수이므로 오른쪽에 쓴다.
9) 자기 자신을 제외한 7의 배수를 모두 지운다.
10) 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.
