[JS] 2022 KAKAO BLIND RECRUITMENT > k진수에서 소수 개수 구하기

function solution(n, k) {
    var answer = n.toString(k).split(0);
    var count = 0;

    for(var i = 0; i < answer.length; i++){
        if(primeChk(answer[i])){
            count++;
        }  
    }
    return count;
}

function primeChk(num){

    if(num <= 1){
        return false;
    }
    
    for(var i = 2; i <= Math.sqrt(num); i++){
        if(num % i == 0){
            return false;
        }   
    }
    return true;
}

n을 k진수로 변환 후 split(0)을 하면 쉽게 원하는 배열을 만들 수 있다.

실제로 코드 자체는 엄청 빨리 구현을 할 수 있었는데 TC 1번에서 계속 시간초과가 떴다.

소수를 찾는 과정에서 2~N까지 계속 나누는 과정이 시간을 많이 소요한다는 것은 알고 있었는데 뭔가 될 것만 같아서 계속 도전해보다 결국 소수를 찾는 함수를 하나 만드는 것으로 해결..

김종도님의 답변이 큰 도움이 됐다.

제곱근까지만 구해도 소수 판별이 가능하다!!

 

+시간초과나는 코드

function solution(n, k) {
    var answer = n.toString(k).split(0);
    var count = 0;

    for(var i = 0; i < answer.length; i++){

        var chk = 0;
        for(var j = 1; j <= answer[i]; j++){

            if(answer[i] % j === 0){
                chk++;
            }
            if(chk > 2){
                break;
            }
        }
        if(chk === 2){
            count++;
        }
        chk = 0;
    }
    return count;
}

처음에 구현한 코드인데 1번에서 계속 시간초과가 떴다..