[백준] 11653. 소인수분해 (node.js/javascript/자바스크립트/알고리즘/코딩테스트)

[백준] 11653. 소인수분해

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	26265	14154	11200	53.331%

문제

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

입력

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

출력

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

 

예제 입력 1

72

예제 출력 1

2

2

2

3

3

 

예제 입력 2

3

예제 출력 2

3

 

예제 입력 3

6

예제 출력 3

2

3

 

예제 입력 4

2

예제 출력 4

2

 

예제 입력 5

9991

예제 출력 5

97

103

 

---

내가 작성한 코드 (자바스크립트)

let fs = require('fs');
let input = fs.readFileSync('예제.txt').toString();
let number = Number(input);
let originNumber = number; // 원래수를 알기 위해 복사해둠
let primenumber = 2;
let smallFactorization = [];

while(true){
    if(originNumber === 1){ // 원래 수가 1이면 반복문 탈출
        break;
    }else{
        if(number !== 1){ // number가 1이 아닐때까지 
            if(number % primenumber === 0){ // 소인수분해 되었을 때
                smallFactorization.push(primenumber);
                number = number / primenumber;
            }else{
                primenumber++;
            }
        }else{ // 나누어서 number가 1이 되면 반복문을 탈출한다.
            break;
        }
    }
}
if(smallFactorization.length !== 0){
    console.log(smallFactorization.join("\n"));
}

주어진 수를 number라는 변수에 할당한다.

원래 수(원본)를 기억해두기 위해 originNumber에 복사를 해둔다. (나중에 반복문을 돌며 number는 소인수분해되어 변하기 때문에)

 

originNumber가 1이라면 반복문을 탈출한다. 즉 원래 수가 1이면 소인수분해 할 것도 없기 때문이다.

그렇지 않다면 계속 반복문을 돌며 소인수분해한다. primenumber는 처음에 2부터 시작하고, 나누어 떨어지지 않는다면 primenumber를 1씩 증가시키면 된다. 그렇게해서 나누어 떨어진다면 smallFactorization이라는 배열에 primenumber를 집어넣고, number는 number를 primenumber로 나눈 값으로 갱신한다.

그렇게 남은 수(number)가 1이 될 때까지 반복문을 계속 돌다가 1이 되면 반복문을 탈출한다.

그리고 마지막으로 smallFactoriaztion의 길이가 0이 아니라면 안의 값들을 출력하면 된다.