소수 찾기 javascript - 프로그래머스

로직

미리 소수를 구해놓고요. 에라토스테네스의 체로 구했습니다.
2~ n까지의 구간중 소수를 구할때 가장 빠른 알고리즘입니다.

모든 순열을 구하고, 배열에 순서대로 저장해요.

출처 : Write a program to print all permutations of a given string - geeksforgeeks

모든 순열을 각각의 문자열에서 해당 문자를 뽑냐 안뽑냐의 문제로 또 풉니다.
그래서 조합으로 구한 수가 소수이면~ 정답의 개수를 +1 씩 갱신해줍니다.

code

function solution(numbers) {

    let answer =0;
    const inputString = numbers.split("");
    const MAX = 10000000;
    const primes = new Array(MAX)
    .fill()
    .map(value => false); // false 소수 
    primes[0] = primes[1] = true;
    
    const numberString = [];
    
    (function getPrimes(){
        for(let i =2; i<MAX; i++){
            if(!primes[i]){
                for(let j = i+i; j <MAX; j+=i){
                    primes[j]=true;
                }
            }
        }
    })();
    
    const checked = 0;
    function permutation(idx,currentString,visited){
        
        if(idx === inputString.length){
            numberString.push(currentString);
            return;
        }
        
        
        for(let i = 0; i< inputString.length; i++){
            if( !(visited & (1<<i)) ){ 
                visited |= (1<<i);
                permutation(idx+1, currentString+inputString[i], visited);
                visited &= ~(1<<i);
            }
        }
    }
    
    
    const checkNumber = {};
    function pick(idx, originalString, currentString){
        if(idx === originalString.length){
            const number = parseInt(currentString);

            if(currentString === ""){
                return;
            }
            
            if(!checkNumber[number]){
                checkNumber[number] = true;
            }else{
                return;
            }

            if(!primes[number]){
                answer +=1;
            }
            return;
        }
        
        pick(idx+1, originalString, currentString);
        pick(idx+1, originalString, currentString+originalString[idx]);
    }
    
    permutation(0,"",checked);
        
    for(const string of numberString){
        pick(0, string, "");
    }
    
    return answer;
}