[Algorithm] 소수 찾기

June 04, 2021 · 4 mins read label-icon Algorithm

프로그래머스 문제 링크

문제 설명

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를 반환

답안

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

function solution(n) {
    // (1)
    let arr = [...Array(n)].map((v,i) => i === 0 ? 0 : i + 1);
    
    // (2)
    for(let i = 2; i * i <= n; i++){
        // (3)
        if(arr[i - 1]){
            // (4)
            for(let j = i * i; j <= n; j += i){
                arr[j - 1] = 0; // (5)
            }
        }
    }
    return arr.filter(v => v !== 0).length; // (6)
}
  1. 매개변수n만큼의 배열 arr을 만들고 첫 번째 항목을 1이 아닌 0으로 변경해준다.
  2. for()를 사용해서 반복문을 실행해준다. (i의 초깃값은 2이고 i의 제곱이 n보다 작을 때까지 실행)
  3. arr[i - 1]의 값이 0이 아닌 경우
  4. for()를 사용해서 반복문을 실행해준다. (j의 초깃값은 i의 제곱, j가 n보다 작을 때까지 실행, j += i)
  5. arr[j - 1]값을 0으로 변경해준다.
  6. 반복문이 종료되고 filter()를 사용해서 배열의 값이 0이 아닌 값을 필터링하고 길이를 반환해준다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

/*

ex) n = 10


1. arr = [0, 2, 3, 4, 5, 6, 7, 8, 9, 10]

2. for(let i = 2; i * i <= n; i++)
    > i = 2, 4 <= n

3. if(arr[i - 1])
    > arr[2 - 1] = 2

4. for(let j = i * i; j <= n; j += i)
    > for(let j = 4; j <= 10; j += 2)

5. arr[j - 1] = 0;
    > arr[4 - 1](4) => 0
    > arr[6 - 1](6) => 0
    > arr[8 - 1](8) => 0
    > arr[10 - 1](10) => 0

6. for(let i = 2; i * i <= n; i++)
    > i = 3, 9 <= n

7. if(arr[i - 1])
    > arr[3 - 1] = 3

8. for(let j = i * i; j <= n; j += i)
    > for(let j = 9; j <= 10; j += 3)

9. arr[j - 1] = 0;
    > arr[9 - 1](9) = 0

10. arr = [0, 2, 3, 0, 5, 0, 7, 0, 0, 0]

11. [2, 3, 5, 7] = 4

*/
← Previous Post Next Post →