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

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

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

제한 조건
n은 2이상 1000000이하의 자연수입니다.
입출력 예
n  result
10 4
5  3
입출력 예 설명
입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

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

 

function solution(n, s=0, a=[]) {
    for(var i=2;i<=n;i++) {
        a[i] = true;
    }
    for(var i=2;i<=n;i++) {
        if(a[i]==false) continue;
        if(a[i]==true) ++s;
        for(var j=2*i;j<=n; j+=i) {
            a[j] = false;
        }
    }
    return s
}
console.log(solution(5));

 

1과 자신만 나눠지는 수를 가져와야하니 일단 하나씩 더해가면 되지만 우선적으로 2,3,5,7... 해당수의 배수를 모두 제거해가면 된다.

 

기본 2를 true로 줘서 개수를 1개 추가한 후 받아온 값이 될때까지 그 배수를 모두 제거해준다. 

'10'을 넣은경우 a[4] 6 8 10 이 false로 제거되서 값이 오르지않고 continue로 넘어가게 된다.

 

다음은 3을 추가한 후 3의 배수를 제거한다. 이경우 6,9가 제거된다.

4의경우는 모두 false가 되어있기에 그대로 넘어간 후 5가 되고 개수가 1개 추가된다.

 

6은 3의 배수로 false가 되어있어 넘어가고 7이 되지만 7의경우 바로 true를하고 x2가 된 경우에 그대로 14가되서 값이 넘기에 사라진다.

 

추가된값은 2,3,5,7 4로 답은 4가된다.

 

값이 5인경우는 3이된다.

 

 

 

for문이 돌아가는 과정으로 보면

i = 2 인경우

 *2를해 4부터 시작해 +=i 가 증감되어 4,6,8,10이 false가 된다.

 

i = 3 인경우

 *2를해 6부터 시작해 +=i 가 증감되어 6,9 가 false가 된다.

 

i = 4 인경우

이미 false라 돌지않는다.

 

i = 5 인경우

5만 true가 되고 10은 이미 false.

 

i = 6 인경우

이미 false라 돌지않는다.

 

i = 7 인경우

7만 true가 되고 14는 10을 넘었기에 넘어간다.

 

뒤도 마찬가지.. 이렇게 소수 구하기가 완료된다.