[LV1] 소수 찾기
데스크탑을 새로 맞췄는데 스피커가 없어 소리가 안난다. 앰프에 연결해보니 됐다. 이왜진?
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)
- n은 2이상 1000000이하의 자연수입니다.
| 10 | 4 |
| 5 | 3 |
입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환
입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환
문제 자체는 쉬웠던 것 같다. 다만....유효성 검사에서 발목을 잡혀 원래 하려던 방식을 구현하지 못하였다.
처음에 생각했던건
- n까지 for문실행(변수 i)
- for문 안에 1부터 i까지 다시 for문을 돌려 약수의 개수를 구함
- 약수의 개수가 2라면 answer에 1을 추가
하는 그저 클래식 그 자체인 방식이었다.
for(let i = 0; i <= n; i++){
let sum = 0
for(let j = 1; j <= i; j++){
if(i % j == 0){
sum++
}
}
if(sum == 2){
answer++
}
}하지만 예시는 통과했지만 정작 테스트 케이스들중 통과를 못하는 것들이 있었다. 왜지?? 웨지감자
무수히 많은 질문이 있길래 들어가 확인해 보니 나처럼 시간초과가 뜨는 분들이 많이 계셨다.
댓글들을 읽어보니 '최적화'를 하여 수행 시간을 줄여야 통과가 된다고 했다. 흠....
확실히 n이 1000000, 100만까지 있다 보니 이중 for문을 돌리기엔 확실히 부담이 될 것 같았다.
그러던 중 여러 팁들 중 에라스토테네스의 체를 이용하라는 이야기가 있었다. 호오?
에라스토테네스의 체는 내가 얼마전에 중1 친구들 소인수분해 가르치면서 봤던 내용이다. 그걸 지금 내가 써야 할 줄이야!
자연수는 모두 소수들의 곱으로 이루어져 있는데, n까지의 정수들 중 소수들의 배수를 모두 지우면 결국 소수만 남는다는 것이다.
과정은 다음과 같다
- 2부터 n까지의 수를 나열
- 2의 배수부터 지워나감
- 2의 배수를 지웠다면 3의 배수를 지움
- 5, 7, ...., 루트 n 미만 소수의 배수를 지움
- 남은 수들은 모두 소수
루트 n 까지만 지워줘도 되는 이유는 길이가 길어지기도 하고, 루트n 이상의 소수의 배수는 이미 지워져 있기 때문이다.
에라스토테네스의 체를 이용해 0부터 50까지의 소수를 찾는다고 하자
2, 3, 5, 7까지의 소수는 배수가 존재하지만 11부터는 이미 배수가 모두 지워진 상태이다. 이들의 배수를 지우기 위해서는 소수*소수 꼴이 필요한데, 50은 2와 5 이외 다른 소수를 가지고 있지 않고, 2와 5의 배수는 이미 지워져 있기 때문에 더이상 곱할 수 있는 수가 없는 것이다.
여튼 이 방식을 기반으로 코드를 구현하기로 했다.
- 1부터 n까지의 수를 담은 배열을 만듬
- 2부터 루트 n까지 for문을 돌림(변수 i )
- i 제곱부터 n까지 for문을 돌림(변수 j)
- j번째 요소는 0으로 바꿈
첫번째 for문은 위에 장황히 설명한대로 루트 n까지의 소수를 찾기 위한 for문이고, 두번째 for문은 찾은 소수의 배수를 찾고, 해당 수를 0으로 바꿔주기 위한 for문이다.
그런데 두번째 for문의 시작 요소가 i * i, 즉 i의 제곱인데, 이는 이미 i보다 작은 소수의 배수들을 모두 찾았기 때문에 i의 제곱부터 시작해준다
예를 들어 i 가 5일때, 이미 5보다 작은 소수인 2, 3에 의해 5*2, 5*3, 5*4는 지워져 있기 때문에 5는 5*5부터 시작해주면 되는 것이다.
let arr = []
for(let i = 0; i <= n; i++){
arr.push(i)
}
arr[0] = 0
arr[1] = 0
for(let i = 2; i < Math.sqrt(n); i++){
for(let j = i * i; j <= n; j += i){
arr[j] = 0
}
}어차피 0과 1은 소수가 아니므로 0으로 설정해 준다
위 과정을 거치면 arr 배열은 [0, 0, 2, 3, 0, 5, ..., 0]의 형태를 가지게 된다.
이제 이 arr 배열 안에서 0이 아닌 요소들의 개수만 세주면 된다.
나는 for문을 이용해 0이 아니면 answer의 개수가 1씩 늘어나는 방법을 사용하였다.
function solution(n) {
var answer = 0;
let arr = []
for(let i = 0; i <= n; i++){
arr.push(i)
}
arr[0] = 0
arr[1] = 0
for(let i = 2; i < Math.sqrt(n); i++){
for(let j = i * i; j <= n; j += i){
arr[j] = 0
}
}
for(let i = 0; i < arr.length; i++){
if(arr[i] != 0){
answer++
}
}
return answer;
}중학생들을 가르치면서 그냥 보고 넘어갔던 개념이 여기서 이렇게 중요하게 작용할 줄은 몰랐다.
나 중학생떄는 배운 기억이 없는데 요즘 생긴거 보면 어릴때부터 IT를 스며들게 하는건가....?