[프로그래머스][JS / Javascript] 소수 찾기

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

프로그래머스

 

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

 

function solution(numbers) {
    const INF = 10000000;

    // 입력값에 들어있는 수의 종류와 갯수
    const numberArr = [0,0,0,0,0,0,0,0,0,0];
    for(let i of numbers) {
        numberArr[parseInt(i)]++;
    }

    // prime[i] = i가 소수인지 여부
    let prime = [];  
    for(let i=0; i<INF; i++) {
        prime.push(true);
    }
    prime[0] = prime[1] = false;
    for(let i=2; i<INF; i++) {
        if(!prime[i]) {
            continue;
        }
        for(let j=i*i; j<INF; j+=i) {
            prime[j] = false;
        }  
    }

    // primeNum 배열 돌면서 해당 소수가 만들어질 수 있는지 카운트
    function makable(target, numbers) {
        for(let i of target) {
            const n = parseInt(i);
            numbers[n]--;
            if(numbers[n]<0) {
                return false;
            }
        }
        return true;
    }

    let ans = 0;
    for(let i in prime) {
        if(!prime[i] || i.length > numbers.length) {
            continue;
        }
        if(makable(i, [...numberArr])) {
            ans++;
        }
    }

    return ans;
}

자바스크립트 특성때문인지는 몰라도 상당히 느리다..

c++로 시도해보거나 다른 방법을 찾아봐야할듯