[알고리즘]뒤집은 소수(소수 판별하기)

문제

n개의 자연수가 입력되면 각 자연수를 뒤집은 후 그 뒤집은 수가 소수이면 그 소수를 출력하세요.

풀이

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

      function solution(arr) {
        let answer = [];
        for (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));

소수 판별

• 소수란 1과 자신만을 약수로 갖는 수로, 1은 소수가 될 수 없다.
• 소수의 조건중에 1과 자기 자신 이외에 나누어 떨어지는 수가 있으면 소수가 아니므로 false를 반환한다.

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

• 만약 16이라는 수가 있을 때, 그 수의 약수 조합은 1*16, 2*8, 4*4, 8*2, 16*1 이 있을 것이다.
• 1과 자기자신을 제외한 2~15의 범위 내에서, 약수는 16의 절반인 8 까지의 범위에 존재한다.
• 또한 16의 제곱근 4를 기준으로 그 이후는 앞서 반복된 것을 뒤집어 반복하는 것이므로, 숫자를 하나씩 돌며 나누어 떨어지는지 판별할 때 이 범위를 Math.sqrt(num)즉 num의 제곱근까지만 반복해주는 것이 효율적이다.

숫자 뒤집기

 function solution(arr) {
        let answer = [];
        for (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;
      }

• while(x) x가 0이 될 때 까지 아래의 코드를 반복한다.
• let t = x%10 x의 일의 자리를 t에 할당한다.
• res = res * 10 +t res에 10을 곱해 원래 값을 왼쪽으로 밀고 t를 더한다
• x = parseInt(x/10) x를 일의 자리를 제외한 몫으로 재할당한다.

function solution(arr) {
        let answer = [];
        for (x of arr) {
          let res = Number(x.toString().split('').reverse().join('');

          if (isPrime(res)) answer.push(res);
        }

        return answer;
      }