소수 구하기

:raising_hand: 알고리즘 공부 간 기록이 필요한 문제들에 대한 정리를 기록하는 포스트 입니다.

1. 문제 요건

주어진 숫자들의 역수를 검사하여 소수임을 확인하라.

2. 코드

// 소수 판별
function isPrime(num) {
    if (num === 1) return false;
    for (let i = 2; i <= parseInt(Math.sqrt(num)); i++) {
        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;
}


function solution2(arr) {
    let answer =[]
    for(x of arr) {
        let reverseNum = ""
        let tmp = x;
        reverseNum = parseInt(x.toString().split('').reverse().join(''))
        if(isPrime(reverseNum)) {
            answer.push(parseInt(reverseNum))
        }
    }
    return answer
}

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

3. 결과정리

이 문제는 난이도가 높다기 보다는 시간복잡도 측면에서 소수를 판별하는데 sqrt 를 통해 전체다 검사하는것이 아니라 제곱근 만큼만 검사를 한다. 약수의 경우 항상 큰수와 작은수가 있기 때문에 작은수를 검사하게 되면 큰수는 당연히 검사가 되는 개념으로 이해하면 될 것 같다. 그런 이유로 sqrt 가 아닌 단순 2로 나누어 검사해도 무방하다.

그리고 주어진 숫자를 역순으로 바꾸는 방법을 2가지 방법으로 풀어보았다. solution2 의 경우처럼 내장함수를 사용하면 손쉽게 변경할 수 있다.

reverseNum = parseInt(x.toString().split('').reverse().join(''))

하지만 내장함수 없이도 풀 수 있도록 하기 위해 다양한 방법으로 연습해야 하기 때문에 solution 에서 사용하여 풀어보았다.

while (x) {
            let t = x % 10;
            res = res * 10 + t;
            x = parseInt(x / 10);
        }

res * 10 + t 알고리즘을 통해서 역순으로 뒤집는 방법인데 이부분을 오늘 처음 알게 되었다. 이부분은 한번씩 그려가며 학습해보는것이 좋을 것 같다.

4. Key Point

  1. 소수 구하기 위한 방법(고난도 알고리즘의 경우 추후 진행)
  2. 내장함수 및 기본 알고리즘 활용

You may also enjoy