[프로그래머스] Lv2 - 소수찾기

var isSosu = new Array(10000000).fill(true)
var visited = new Array(10).fill(false)
var answer = 0;
var overlay ={}

function combine(numbers,num,depth){
    
    if(depth == numbers.length){
        return;
    }
    
    for(let i = 0; i < numbers.length; i++){
        if(visited[i]) continue;
        num.push(numbers[i])
        visited[i] = true
        const k = parseInt(num.join(''))
        if(isSosu[k] && !overlay[k]){
            overlay[k] = true
            answer++
        }
        combine(numbers,num,depth+1)
        visited[i] = false
        num.pop()
    }
}    

function solution(numbers) {
    
    isSosu[0] = false
    isSosu[1] = false
    for(let i = 2; i < 10000000; i++){
        if(isSosu[i] == false) continue;
        for(let j = i * 2; j < 10000000; j += i){
            isSosu[j] = false
        }
    }
    
    numbers = numbers.split('')
    combine(numbers,new Array(),0)
    
    return answer;
}

에라토스테네스의 체를 이용해서 먼저 소수를 검사할 수 있는 배열을 구한다음.
스트링을 배열로 쪼갠다음 DFS를 이용해서 만들 수 있는 모든 숫자를 다 구했다.
구한 숫자들을 다시 합쳐서 소수인지 체크와 overlay객체를 이용해서 중복체크를 했다.
시간복잡도는 (N^M)정도 될듯