[프로그래머스][브루트 포스] k진수에서 소수 개수 구하기

     

목차

 

문제

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

프로그래머스

 

 

코드 구현 방향

전에 모든 약수를 구할때 i*i까지 순회하여 루트 시간복잡도로 시간을 단축한 기억이 있어서 쉽게 풀었다.

조건을 쉽게 이해해 보면 문자열을 0을 기준으로 쪼개서 모든 수를 탐색해 보라는 것이었다.

 

 

코드 구현

function solution(n, k) {
    var answer = 0;
    let str = convert(n, k);
    let arr = str.split("0").map(Number);

    arr.forEach((item)=>{
        if(judge(item))answer++;
    })
    
    return answer;
}


function judge(num){
    if(num === 1 || num===0)return false;
    if(num === 2 || num === 3 || num === 5 || num === 7) return true;
    for(let i=2; i*i<=num; i++){
        if(num % i === 0)
            return false;
    }
    return true;
}


function convert(num, dv){
    let arr = [];
    let str ="";
    while(num >0){
        arr.push(num%dv);
        num = Math.floor(num/dv);
    }
    arr.reverse().forEach((item)=>str+=item);
    return str;
}