프로그래머스 JavaScript [소수 찾기] 소수판별

• 소수 찾기

문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

제한 조건

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

입출력 예nresult

10	4
5	3

입출력 예 설명

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

---

제출한 답

 

function solution(n) {
    const prime = (a) => {
        for (let i = 2; i <= Math.sqrt(a); i++) {
            if (a % i == 0) return false;
        }
        return true;
    };

    var answer = 0;

    for (let i = 2; i <= n; i++) {
        if (prime(i)) answer++;
    }
    return answer;
}

 

for 문에 ( let i = 2 ) 와 단순 ( i = 2 ) 로 했을 때의 차이를 알게 되었습니다.

함수를 다른 함수 안으로 불러올 때는 같은 지역스코프 안에 포함되는 것이기 떄문에

상위의 for문에서 i 를 매개변수로 썼다면 하위의 for문은 i 를 새로 불러오지 않고,

상위의 for문에서 쓰인 i 의 값을 가져다 쓰게 되는 듯 합니다.

따라서 앞으로는 오류를 방지하기 위해 let i = 2 와 같이 let으로 선언하는 방식을 고수해야겠습니다.

 

 

 

소수판별은 처음 보면 이해가 잘 안됩니다.

    const prime = (a) => {
        for (let i = 2; i <= Math.sqrt(a); i++) {
            if (a % i == 0) return false;
        }
        return true;
    };

어떻게 작동하고 있는지 a에 들어가는 값을 예로 듭니다.

a = 2를 넣었을 때 for 문의 범위는 루트2 인데,  i=2로 이보다 큰 수로 시작기 때문에 곧바로 for문을 종료해 true를 반환합니다.

a = 3또한 루트3의 범위보다 i=2가 더 큰 수로 시작하여 마찬가지로 for문을 즉시 종료해  true를 반환합니다.

a = 4... ( 4 % 2 == 0 ) 조건으로 false를 반환합니다.

a = 5... ( 5 % 2 == 1, 5 % 3 == 2, 5 % 4 == 1 ) 조건으로 0이 되는 경우가 없으므로 for문을 종료하고 true를 반환합니다.

a = 6... ( 6 % 2 == 0 ) 조건으로 false를 반환합니다.

a = 7... ( 7 % 2 == 1, 7 % 3 == 1, 7 % 4 == 3, 7 % 5 == 2, 7 % 6 == 1 ) 조건으로 0이 되는 경우가 없으므로 true를 반환합니다.

... 

 

이는 에라토스테네스의 채라고 하여,

2는 소수, 그리고 2의 배수를 모두 제하고,

3은 소수, 그리고 3의 배수를 모두 제하고,

4(는 2의 배수로 제해집니다.)

5는 소수, 그리고 5의 배수를 모두 제하고,

6(은 2의 배수로 제해집니다.)

7은 소수, 그리고 7의 배수를 모두 제하고,

...

이와 같은 과정을 거치며 남게 되는 수들은 소수가 된다는 방식으로 소수를 판별합니다.

여기서 반복 범위로 Math.sqrt(a)를 쓰는 이유는 소수를 판별할 때는 그 수의 제곱근 까지만 확인하면 되기 때문입니다.