프로그래머스 소수찾기 자바스크립트: 빠르게 소수를 찾는 방법

프로그래머스 level1 소수찾기는 언뜻보면 간단한 구현문제처럼 보이지만, 정수론을 모른다면 시간초과로 인해 해결할 수 없는 문제이다.
비록 level1 문제이지만, 이후 level2 소수찾기처럼 소수를 활용한 문제를 풀 때에도 요긴하게 쓰일 것 같아 따로 정리해보았다.


다음은 소수를 찾는 데 사용되는 간단한 법칙을 이용한 풀이이다.

• 1보다 큰 모든 자연수는 소수의 곱으로 이루어져 있다.
  따라서 100이 소수인지 확인하기 위해서는 100보다 작은 소수를 이용하면 된다.
• 자연수 n이 있을 때 √n 보다 작은 수로 나눠 떨어지지 않으면 n은 소수이다.
• 2보다 큰 모든 짝수는 2로 나누어 떨어지는 소수가 아닌 수이다.

level1 소수찾기

자바스크립트 문제풀이

function solution(n) {
  let answer = [];
  
  function isPrime (n) {
    for(let x of answer) {
      if(x>Math.sqrt(n))return true
      if(Number.isInteger(n/x)) return false
    }
    return true
  }
  
  for(let i=2; i<=n; i++) {
		if(!i%2) continue
    if(isPrime(i)) answer.push(i)
  }
  
  return answer.length;
}

• isPrime은 answer 배열의 값과 유무를 통해 소수를 판별하는 함수이다.
• Math.sqrt(n)을 이용해 for문을 최소화한다.
• 소수는 answer 배열로 들어가므로, answer로 나눴을 때 정수로 떨어진다면 소수가 아닌 수이다.
  
  

level2 소수찾기

자바스크립트 문제풀이

function solution(numbers) {
  let answer = 0;
  const primes = new Set();
  const check = Array.from({ length: numbers.length }, () => 0);

  function DFS(s, L, check) {
    if (L === numbers.length) {
      s && primes.add(Number(s));
      return
    } else {
      for (let i = 0; i < numbers.length; i++) {
        if (!check[i]) {
          check[i] = 1;
          DFS(s+numbers[i], L+1, check)
          DFS(s, L+1, check)
          check[i] = 0;
        }
      }
    }
  }
  DFS("", 0, check);
  
  function isPrime(n) {
    if(n<=1) return false
    for (let i = 2; i <= Math.sqrt(n); i++) {
      if (Number.isInteger(n/i)) {
        return false
      }
    }
    return true;
  }

  for (let x of primes) {
    isPrime(x) && answer++;
  }
  
  return answer;
}

console.log(solution("17")); // 3
// console.log(solution("011")); // 2

소수찾기 + DFS 응용문제로, DFS를 이용하여 제시된 숫자종이로 만들 수 있는 숫자를 만들어야 하는 부분에서 애를 먹었다.

그림을 그려보니 레벨과 check배열을 사용하면 되겠구나 싶어서 풀 수 있었다. 중복제거를 위해 Set를 사용하였고, 더 빠르게 구현하려면 가장 큰 수로 만든 소수를 이용해 그보다 작은 수에 적용하는 방식도 사용할 수 있겠다.

---

참고사이트: 프로그래머스 질문목록, 소수찾기level1, 소수찾기 level2