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

코테 문제를 풀다가 시간초과가 떴다. 테스트케이스는 금방 통과했는데,

1~8번 테스트케이스도 통과했는데, 9~12번은 시간초과가 떴다. 

아마 답 자체는 맞았겠지만, 반복문을 3중으로 돌리고,

그 안에 조건문도 있고 여러 경우가 들어있어서 복잡해서 그런게 아닌가 싶다.

 

조금 간추려보기도 했는데, 각 수의 약수를 한 배열에 담아서 1과 자신이 바로 나오면

(소수의 조건대로) answer에 누적해보기도 했지만 10~12번이 시간초과가 떴다. 

조건을 살펴보니 n은 2이상 1000000이하의 자연수이다. 

어떻게 해도 알고리즘 생각하지 않고 풀면 시간초과가 뜨는 것 같다.

 

소수를 구하는 방법은 다양하겠지만 에라토스테네스의 체를 이용한 풀이가 일반적인 것 같다. 

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

자세한 설명은 위를 참조하면 좋을 것 같다. 

 

간단하게는, 소수의 배수를 다 걸러내는 것이다. 먼저 1은 소수가 아니고,

2는 1과 자신만을 약수로 가지는 수이다. 그렇다면 2의 배수는 소수가 아니다.

3은 1과 자신만을 약수로 가지는 수이다. 그렇다면 3의 배수는 소수가 아니다. 

4는 2의 배수이므로 소수가 아니다.

5는 1과 자신만을 약수로 가지는 수이다. 그렇다면 5의 배수는 소수가 아니다. 

6은 2,3의 배수이므로 소수가 아니다. 

7은 1과 자신만을 약수로 가지는 수이다. 그렇다면 7의 배수는 소수가 아니다. 

8은 2,4의 배수이므로 소수가 아니다. 

9는 3의 배수이므로 소수가 아니다. 

이런식으로 소수의 배수를 미리 걸러낸다. 2,3,5,7의 배수는 거른다. 

 

function solution(n) { 
    let arr = [] 
    // 1) 2부터 소수가 될 수 있으므로, 2부터 시작하는 배열을 만든다. 
    for (let i = 2; i <= n; i++) { 
        arr[i] = i 
    } 
    // 2) 2의 배수 이상의 숫자를 모두 지우되, 이미 지워진 숫자는 건너뛴다. 
    for (let i = 2; i <= n; i++) { 
        for (let j = i + i; j <= n; j += i) { 
            if (arr[j] === 0) { 
                continue 
            } 
            arr[j] = 0 
        } 
    } 
    return arr.filter((item) => item !== 0).length 
}

1) arr[i]=i 로 반복하게 되면, i가 2부터 시작되는데, arr[2]부터 i값을 넣게 되기 때문에

arr[0]~[1]에는 null이 된다. 그런데 arr.push(i)로 하지 않는 이유는, 이어지는 반복문에서

조건에 맞게 (소수의 배수) 지워주려 하는데, 시작점을 동일하게 해야 같은 위치의 숫자를

지우고 소수만 남길 수 있기 때문이다. 

 

그래서 j에는 i의 배수를, 그리고 j는 i의 배수이기 때문에 i만큼 값을 늘렸다.

i가 3일 때 j는 6이되고, 6부터 3씩 늘어난다. 

 

해당 수가 이미 0일 경우 건너뛰는데, i만큼 늘어나는 j의 값을 모두 0으로 만들어준다. 

이후 값을 반환할 때는 소수를 제외한 수는 0이 되어있으므로 0을 빼고 반환한다.