[JS로 코테 준비하기] 15. 소수 찾기(feat. 에라토스테네스의 체)

https://school.programmers.co.kr/learn/courses/30/lessons/12921

프로그래머스

 

제한 범위가 크지 않아 단순히 반복문을 돌리면 될 것 같았는데, 효율성 테스트가 있는 문제였다.

소수를 구하는 방식 자체는 여기에서 다루었는데, 특이한 상황을 마주해서 이를 공유하고자 한다.

 

방법 1. O(√N)

• 2부터 √N까지 나눠보기

const isPrime = (n) => {
    if(n < 2) return false;
    for(let i = 2; i*i <= n; i++){
        if(n % i === 0) return false;
    }
    return true;
}

 

위 방식으로 하면 효율성 테스트에서 시간초과가 발생한다.

 

 

방법 2. O(NloglogN)

• 에라토스테네스의 체
• 소수는 1과 자기 자신(n)으로만 나누어지는 수 = n이 2부터 n-1까지의 수로 나누어 떨어지면 소수가 아님

const MAX = 1000001;
const check = Array(MAX).fill(false); //false면 소수

const isPrime = () => {
    check[0] = check[1] = true;
    for(let i = 2; i * i <= MAX; i++){
        if(!check[i]){
            for(let j = i + i; j <= MAX; j+=i)
                check[j] = true;
        }
    }
}

//참고) n을 인자로 넘기고, MAX부분을 n으로 바꿔도 됨

 

시간 복잡도가 줄었기 때문에, 효율성 테스트도 문제가 없다.

 

 

방법 3. O(NloglogN)

• 두 번째 반복문에 조건을 걸어 처리한 것이 인상적인 풀이
• 마찬가지로 효율성 테스트 통과에 문제가 없다.

const isNotPrime = (n) => {
    const check = [...Array(n).keys()]; //0이면 소수
    for(let i = 2; i * i <= n; i++){
        for(let j = 2; j <= (n-i)/i + 1; j++){
            check[i * j - 1] = 0;
        }
    }
    return check;
}

 

 

소스 코드

const MAX = 1000001;
const check = Array(MAX).fill(false);

const isPrime = () => {
    check[0] = check[1] = true;
    for(let i = 2; i * i <= MAX; i++){
        if(!check[i]){
            for(let j = i + i; j <= MAX; j+=i)
                check[j] = true;
        }
    }
}

function solution(n) {
    isPrime();
    return [...Array(n+1).keys()].slice(2).reduce((cnt, cur) => check[cur] ? cnt : cnt + 1, 0);
}

 

 

의문점 한 가지

위 소스 코드를 통해 테스트를 통과했다. 그리고 다른 사람들의 코드를 보다가 reduce 대신 filter를 사용하는 게 더 깔끔해 보여 다시 돌려봤는데.. 마지막 효율성 테스트에서 시간 초과가 발생했다. 🤨

 

왜??

 

이것저것 해보다가 우연히 return 위에 주석을 추가한 상태(위와 코드는 동일)로 제출하기를 클릭했는데, 이건 또 잘 통과가 되었다. (???)

 

음.. 잠깐 프로그래머스에서 오류가 난 건가?? 싶기도 하고, 뭐가 문제였는지 잘 모르겠다.

처음 보는 상황이라 당황스러워서 남겨둔다.