[프로그래머스][JS / Javascript] k진수에서 소수 개수 구하기

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

프로그래머스

 

풀이

function solution(n, k) {
    function isPrime(num) {
        if(num === 1)
            return false;
        for(let i=2; i<Math.sqrt(num); i++) {
            if(num%i === 0)
                return false;
        }
        return true;
    }
    
    let ans = 0;
    let arr = n.toString(k).split("0");
    for(let i of arr) {
        if(i !== '' && isPrime(parseInt(i)))
            ans++;
    }
    return ans;
}

 

시행착오

매번 소수 구하려고 반복문 도는게 너무 비효율적이게 보여서

에라토스테네스의 체를 이용하여 소수여부를 바로 반환해주는 배열을 만들어서 풀이했는데

1번, 12번, 15번 테케에서 틀렸다고 계속 떠서 포기했다 ㅠㅠ

    // isPrime[num] = num이 소수인가?
    const INF = 1000000;
    let isPrime = [];
    for(let i=0; i<=INF; i++) {
        isPrime.push(true);
    }
    isPrime[0] = isPrime[1] = false;
    for(let i=2; i<=INF; i++) {
        if(!isPrime[i]) {
            continue;
        }
        for(let j=i*i; j<=INF; j*=i) {
            isPrime[j] = false;
        }
    }