[백준 11653번 소인수분해 - node.js] [알고리즘 기초 1/2]

https://www.acmicpc.net/problem/11653

11653번: 소인수분해

 

문제

 

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

 

입력

 

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

 

출력

 

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

 

예제 입출력

 

입력	출력
72	2 2 2 3 3

 

풀이[node.js]

 

 

728x90

소인수분해하는 과정을 그대로 코드로 옮겼습니다.

2부터 유효하기 때문에, i를 2부터 해서 num값으로 넣어주고(그냥 i를 num처럼 써도 됨), result를 num으로 나눈 나머지 값이 0이라면 answer에 num값을 넣어줍니다. 만약 result를 num으로 나눈 몫이 1이라면 해당 inputs에 대한 소인수분해과정이 끝난 것이므로, break;를 걸어줍니다.

만약 몫이 1이 아니라면 몫을 result에 다시 대입해줍니다. (예) inputs=2일 때, 2%2=0이고, 2/2=1이므로, 답이 2가되야함, 몫이 1이 된 경우, 소인수분해가 끝난것임)

그럼, 2로 나눌 수 있는 만큼 나눈 후, 다시 i가 3으로 올라가서 3으로 나눌 수 있는 만큼 나누게 됩니다.

이와 같은 방식으로 몫이 1이 될 때까지 inputs을 나누어주면, answer에 나눠진 몫들이 다 들어가게 되고, 이 값을 출력해주면 됩니다.

var fs = require('fs');
var inputs = fs.readFileSync('/dev/stdin').toString();
var answer = [];
var result = inputs;
for(var i=2; i<=inputs; i++){
    var num = i;
    while(result%num === 0){
   		answer.push(num);
        if(result/num === 1) break;
        result = result/num;
	}
}
console.log(answer.join('\n').trim());