[js] 프로그래머스 - 소수 찾기

프로그래머스 lv.1 소수 찾기

 

1) n이 1과 2일 때의 경우를 따로 빼주었다. 1과 2인 경우를 제외하면 규칙적인 코드 작성이 더 간편해지기 때문이다.

if (n == 1) return 0;
if (n == 2) return 1; //n=2일 때는 자기 자신이 소수이므로

 

 

2) n이 3 이상일 때의 경우 3부터 n까지 for문을 걸어 카운트업 해준다. (소수 합성수 구분 없이 우선 세어 줌)

이때 각 i에 대하여 2부터 i의 제곱근까지의 수로 i를 나누어보고 나누어떨어진다면 소수가 아니므로 카운트다운 해준다.

이때 i의 제곱근 대신 i / 2로 해도 가능은 하나 시간 초과가 뜬다. (더불어 효율성 테스트도 모두 실패)

for (i = 3; i <= n; i++) {
        answer++;    
        end: for (j = 2; j <= Math.sqrt(i); j++) {
            if (i % j == 0) {
                answer--; break end;
            }
        }
    }

 

처음엔 break를 잘 사용할 줄 몰라 애먹었었는데, 이번에 다시 사용해봤다. i를 2부터 i의 제곱근까지의 수로 나누었을 때 한 번이라도 나누어떨어진다면 소수가 아니므로 더 이상 for문이 돌지 않도록 블록에 break를 걸었다. 아주 좋은 선택이었다. 이것 때문인지 아니면 채점 기준이 좀 바뀐 건지 몰라도 시간 초과 떴다는 분들이 많았는데 나는 효율성 테스트까지 무사히 통과했다. (뿌듯!)

 

 

마무리.

function solution(n) {
    var answer = 0;
    
    if (n == 1) return 0;
    if (n == 2) return 1;
    
    for (i = 3; i <= n; i++) {
        answer++;
        end: for (j = 2; j <= Math.sqrt(i); j++) {
            if (i % j == 0) {
                answer--; break end;
            }
        }
    }
    
    return answer + 1;
}

 

마지막  return에 answer + 1인 이유는 전체 for문에서 i를 3부터 돌리기 때문에 2를 제외하고 카운트업 해주어서 그렇다. 2는 소수이기 때문에 마지막에 2의 카운트 +1을 한 것이다.