(알고리즘) 뒤집은 소수

N개의 자연수가 입력되면 각 자연수를 뒤집은 후 그 뒤집은 수가 소수이면 그 소수를 출력하는 프로그램을 작성하세요 예를 들어 32를 뒤집으면 23이고, 23은 소수이다. 그러면 23을 출력한다. 단 910을 뒤집으면 19로 숫자화해야한다. 첫 자리부터 연속된 0은 무시한다.

입력설명

첫 줄에 자연수의 개수가 N(3<=N<=100)이 주어지고, 그 다음줄에 N개의 자연수가 주어진다. 각 자연수의 크기는 100,000을 넘지 않는다.

출력설명

첫 줄에 뒤집은 소수를 출력한다. 출력순서는 입력된 순서대로 출력한다.

입력예제

[32, 55, 62, 20, 250, 370, 200, 30, 100]

출력예제

[23, 2, 73, 2, 3]

문제풀이

함수형 프로그래밍을 본격적으로 사용해서 풀어야 하는 문제이다.
먼저 입력된 배열의 각 요소를 뒤집어야 하기 때문에, forEach()를 이용해 각 요소에 접근해주었다.

그리고 난후 s.toString().split('').reverse().join('')으로 자릿수를 뒤바꾸어 주었다.

문제의 설명처럼 0이 앞에오면 무시해야하기 때문에, 정수를 반환하는 내장함수인 parseInt()를 사용해 0이 백 혹은 십의 자리에 위치할 경우 제거해주었다.

관건은 소수를 판별하는 것이다. 소수는 1과 그자신만을 약수로 가지는 수를 말한다.

인자로 받은 값이 소수인지 판별하는 함수 isPrime() 안에선 먼저 플래그를 만들어 주었고, 2부터 숫자 전까지 그 숫자를 나눴을때 나머지가 0일 경우 false를 반환해주고, 그렇지 않다면 true를 의미하는 isPrime변수(true)를 리턴하도록 함수를 작성했다.

function solution(arr) {
  let answer = [];
  let conversionArr = arr.forEach(item => {
    const conversionNum = parseInt(item.toString().split('').reverse().join(''));
    if (isPrime(conversionNum)) {
      answer.push(conversionNum);
    };
  });
  return answer;
}

function isPrime(x) {
  const isPrime = true
  if (x === 1) {
    return !isPrime;
  }
  for (let i = 2; i < x; i++) {
    if (x % i === 0) {
      return !isPrime;
    }
  }
  return isPrime;
}

const arr = [32, 55, 62, 20, 250, 370, 200, 30, 100];

console.log(solution(arr));

다른 문제 풀기

😇 에라토스테네스의 체
모든 자연수는 소수들의 곱으로 표현이 된다. 제일 작은 소수는 2부터 시작하는데, 2부터 N-1까지의 수중에 2의 배수를 모두 거르고, 남은 숫자들 중에서 3의 배수를 거르고를 반복해서 제곱근 N까지 걸리지지 않은 남은 수들은 모두 소수가 된다.

에라토스테네스의 체를 이용해서 문제를 풀 수 있다.

function solution(arr) {
  let answer = [];
  let conversionArr = arr.forEach(item => {
    let conversionNum = 0;
    while (item) {
      let t = item%10; // 10의 자리 구하기 
      conversionNum = conversionNum * 10 + t; // 앞뒤 바꾸기 
      item = parseInt(item/10);
    }
    if (isPrime(conversionNum)) {
      answer.push(conversionNum);
    };
  });
  return answer;
}

function isPrime(x) {
  const isPrime = true
  if (x === 1) {
    return !isPrime;
  }
  for (let i = 2; i <= Math.sqrt(x); i++) {
    if (x % i === 0) {
      return !isPrime;
    }
  }
  return isPrime;
}

const arr = [32, 55, 62, 20, 250, 370, 200, 30, 100];

console.log(solution(arr));