[알고리즘] 소수 찾기

문제 설명

 

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

numbers	result
"17"	3
"011"	2

입출력 예 설명

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

• 11과 011은 같은 숫자로 취급합니다.

나의 풀이

let numbers = "011";

function makeNum(numbers, arr, str) {
  if (numbers.length === 0) {
    return;
  }

  for (let i = 0; i < numbers.length; i++) {
    let num = parseInt(str + numbers[i]);
    makeNum(
      numbers.filter((data, idx) => {
        return idx !== i;
      }),
      arr,
      num
    );

    if (num > 1) arr.add(num);
  }
}

function solution(numbers) {
  var answer = 0;

  let arr = new Set();

  makeNum(numbers.split(""), arr, "");

  arr.forEach((element) => {
    let check = true;
    for (let i = 2; i <= parseInt(Math.sqrt(element)); i++) {
      if (element % i === 0) {
        check = false;
      }
    }
    if (check) {
      answer++;
    }
  });

  return answer;
}

solution(numbers);

소수를 판별하는 방법 중 제곱근을 사용하는 방법이 있다. 

 

N = a * b 에서 a 와 b는 모두 N의 제곱근 보다 작다는 공식이다. 

 

해당 공식을 적용해서 문제를 푸니 쉽게 풀렸다.