백준 11653 javascript | node.js

문제

문제 출처 - https://www.acmicpc.net/problem/11653

11653번: 소인수분해

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

 

** N 이 1인 경우에는 아무것도 출력하지 않는다.

풀이

소수인 지 판별하는 isPrime 변수를 만들고, 함수처럼 이용한다.

(소수를 활용하는 알고리즘 문제에서 유용하게 사용할 예정, 이해 후 암기)

 

두 가지 케이스로 나누어 생각했다.

 

Case I. N 이 이미 소수인 경우

=> 소수 출력

 

Case II. N이 소수가 아닌 경우

=> i = 2 부터 시작하는 while문을 이용.

     N % i 가 0 인 경우, arr에 넣는다.

     N 이 i 와 같아질 때 loop를 빠져나온다.

 

코드

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs.readFileSync(filePath).toString().split('\n');

// 소수 판별
const isPrime = (n) => {
    if (n === 1) {
        return false;
    }

    for (let i = 2; i <= Math.sqrt(n); i++) {
        if (n % i === 0) {
            return false;
        }
    }

    return true;
}

let n = +input[0];
let arr = [];

// CaseI. 이미 소수인 경우
if (isPrime(n)) {
    console.log(n);
}

// CaseII. 주어진 수가 소수가 아닌 경우
else {
    for (let i = 2; i <= n; i++) {
        while(n % i === 0) {
            arr.push(i);
            n /= i;
        }

        if (n === i) break;
    }

    console.log(arr.join('\n'));
}