[백준 / Node.js] 11653번: 소인수분해📌

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

입력

첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

출력

N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

예제 입력1

72

예제 출력1

2
2
2
3
3

예제 입력2

3

예제 출력2

3

예제 입력3

9991

예제 출력3

97
103

답(시간초과ㅠㅠ)

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

let num = +input[0];
let div = 2;

while (true) {
  if (num % div === 0) {
    num = num / div;
    console.log(div);
    if (num === 1) break;
  } else {
    div++;
  }
}

소수를 신경쓰지 않고 iterator를 2부터 sqrt(N) 까지 증가시키며 나누어 떨어지는 경우에 출력하고 N은 몫으로 감소시킨다

답( sqrt() 이용 )

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

let num = input[0];

for (let i = 2; i <= Math.sqrt(num); i++) {
  while (num % i === 0) {
    console.log(i);
    num /= i;
  }
}
if (num !== 1) console.log(num);