프로그래머스 [Lv. 2] 소수 찾기 {언어 : JavaScript}

문제 링크

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

프로그래머스

정답 코드

function solution(numbers) {
    const lenNumbers = numbers.length;
    const resultArr = new Set();
    const dfs = (l, v, str) => {
        if (l == lenNumbers) {
            resultArr.add(Number(str.join("")))
            return
        }
        for (let idx = 0; idx < lenNumbers; idx++) {
            if (v.includes(idx)) {
                continue
            }
            dfs(l+1, [...v, idx], [...str, numbers[idx]])
            dfs(l+1, [...v, idx], str)
        }
    }
    dfs(0, [], [])
    const eratostenes = (number) => {
        if (number <= 1) {
            return false
        }
        for (let num = 2; num <= number ** 0.5; num++) {
            if (number % num === 0) {
                return false
            }
        }
        return true
    }
    const answer = Array.from(resultArr).reduce((prefix, num) => {
        if (eratostenes(num)) {
            prefix += 1
        }
        return prefix
    }, 0);
    return answer;
}

풀이 방법

1. dfs로 조합을 만든다.
2. 중복된 수를 set에서 제거한다.
3. resultArr에서 소수인 수를 찾아서 prefix에 + 1을 해준다.
   1. 에라토스테네스의 채로 소수를 거른다.

느낀점

• 에라토스테네스의 체...