[프로그래머스 lev1/JS] 소수 만들기

문제 출처

프로그래머스 lev1 - 소수 만들기

문제

나의 풀이

소수 판단할 때 방법들
만약 1~n까지 전부 for문을 돌 경우 cnt≤2일 때 소수이고
1~Math.sqrt(n)을 순회한다면 cnt≤1이 맞음
근데 여기서 1은 어차피 무조건 돌테니까
2~Math.sqrt(n)을 순회한다면 cnt==0이 맞음.

if (L===3) {
      // let jud=true;
      let cnt=0;
      let sum=tmp.reduce((a,b)=>a+b,0);
      for (let j=2; j<=Math.sqrt(sum); j++) {
        if (sum%j===0) cnt++;
      }
      if (cnt===0) answer++; 
}

재귀를 통한 풀이

function solution(nums) {
  
  let ch = Array.from({length:nums.length}, () => 0);
  let tmp = [];
  let idx=0;
  let answer=0;

  function Sum (L) {
    if (L===3) {
      let jud=true;
      let sum=tmp.reduce((a,b)=>a+b,0);
      for (let j=2; j<=Math.sqrt(sum); j++) {
        if (sum%j===0) jud=false;
      }
      if (jud) answer++; 
    }
    else {
      for (let i=idx; i<nums.length; i++) {
        if (ch[i]===0) {
          ch[i]=1;
          tmp[L]=nums[i];
          idx=i+1; 
          Sum(L+1);
          ch[i]=0;
          tmp.pop();
        }
      }
    }
  }
  Sum(0)
  return answer;
}

console.log(solution([1, 2, 7, 6, 4]));