브루트 포스 - 뒤집은 소수

문제 자체는 간단하다.

배열의 모든 요소를 뒤집어 소수인지 판단하고, 소수이면 출력하는 문제이다.

 

예를 들어 52라는 값이 들어오게 되면, 25로 뒤집은 다음에 해당 숫자가 소수인지 판단하기 위해서 1부터 25까지 차례대로 25에 나눈다. 이때 나머지가 0인 수가 존재한다면, 해당 자연수는 25의 약수이다. 최종적으로 1과 자기자신인 25를 제외하고 약수가 존재하게 된다면 25는 소수가 아니게된다.

 

간단한 이 문제를 정리하는 이유는 바로 순회할 때 1부터 25까지 모두 순회할 필요가 없기 때문이다.

 

예시를 16으로 바꾸어 설명해보자.

 

1 X 16 = 16

2 X 8 = 16

4 X 4 = 16

8 X 2 = 16

16 X 1 = 16

 

약수들의 조합으로 16을 다음과 같이 표현할 수 있다.

이때 4 X 4를 기준으로 밑에 있는 것들은 위에 있는 것들을 그저 뒤집어 준 것이다.

즉, 1과 자기자신인 16을 제외했을 때 가장 크게 약수로 나올 수 있는 수는 16을 2로 나눈 8이다.

그렇기 때문에 순회할 때 16까지 순회할 필요가 없다. 그 절반인 8까지만 순회한다면, 나머지는 이미 순회했던 것들을 뒤집은 것들이기 때문이다.

 

그렇기 때문에 2부터 8까지만 순회해서 16의 약수인지만 판단하면 된다.

function isPrime(num) {
  if (num === 1) return false;
  for (let i = 2; i <= parseInt(Math.sqrt(num)); i += 1) {
    if (num % i === 0) return false;
  }

  return true;
}

 

때문에 제곱근을 이용해서 2부터 num에 제곱근을 씌운 값까지만 순회하면 해당 num이 소수인지 아닌지 판단할 수 있게된다.

 

최종 코드는 다음과 같다.

function isPrime(num) {
  if (num === 1) return false;
  for (let i = 2; i <= parseInt(Math.sqrt(num)); i += 1) {
    if (num % i === 0) return false;
  }

  return true;
}

function solution(arr) {
  let answer = [];
  for (let x of arr) {
    let res = 0;
    while (x) {
      let t = x % 10;
      res = res * 10 + t;
      x = parseInt(x / 10);
    }
    if (isPrime(res)) answer.push(res);
  }
  return answer;
}

let arr = [32, 55, 62, 20, 250, 370, 200, 30, 100];
console.log(solution(arr));