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

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

프로그래머스

---

1) 풀이

소수 찾는 알고리즘 + dfs로 순열 풀듯이 푸는 방식을 사용했다

소수 찾는 알고리즘은 이전에 풀어본 적이 있었고 순열 풀이도 예전 휴학때 해본 적 있으나 잊고 살다가

코테 준비한다고 급하게 풀어보는 중..

나중에 참고하려고 참고했던 자료를 첨부한다

자료 보면 풀이 이해가기 때문에 따로 적지는 않음! 

2) 최종 소스코드

function solution(numbers) {
  let answer = 0;
  const done = [];
  const arr = [...numbers];
  const select = Array.from({ length: arr.length }, () => false);
  function prime(k) {
    if (done.includes(k) || k === 0 || k === 1) return;
    for (let i = 2; i * i <= k; i++) {
      if (k % i === 0) return;
    }
    answer++;
    done.push(k);
  }
  function dfs(count, n) {
    prime(Number(n));
    if (count >= arr.length) return;
    for (let i = 0; i < arr.length; i++) {
      if (select[i]) continue;
      select[i] = true;
      dfs(count + 1, n + arr[i]);
      select[i] = false;
    }
  }

  dfs(0, "");
  return answer;
}

3) 참고자료

https://rimkongs.tistory.com/115

[개념] 조합, 순열 + DFS,BFS

https://myjamong.tistory.com/139

소수(Prime Number) 구하기 효율적 알고리즘 :: 코드자몽