[Baekjoon] 11653 소인수분해(자바스크립트/NodeJs)

이번 문제는 아래 링크에서 풀어볼 수 있습니다.

11653번: 소인수분해

---

🤔 문제

정수 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

---

정답 코드

답안 1

답안 2

---

문제 풀이

 소인수분해는 1보다 큰 자연수를 소인수들만의 곱으로 나타내는 것 또는 합성수를 소수의 곱으로 나타내는 방법을 말한다. 여기서 소인수란 어떤 정수(整數)를 소수(素數)만의 곱으로 나타낸 때의 각 인수(因數). `12＝2✕2✕3'에서 `2'와 `3' 등이다.

 소인수분해를 코드로 구현하려면 주어진 수에 나눗셈을 했을 때 나누어 떨어지는 소인수들을 구하는 로직을 짜면 된다. 즉 72가 주어졌을 때 계산은 다음과 같이 이루어진다.

72 / 2 === 36 … 0
36 / 2 === 18 … 0
18 / 2 === 9 … 0
9 / 3 === 3 … 0 (여기서 소수 2로는 나눠떨어지지 않기 때문에 또다른 소수 3으로 나눗셈을 하는 소수를 변경한다.)
3 / 3 === 1 … 0 (나눗셈의 결괏값이 1이 될 때까지 위 작업을 수행하면 된다.)

즉 num이 1이 될 때까지 기존의 num을 num / i 로 치환하는 작업을 반복하면 되는 것이다.

---

함께 보기

https://gigibean.tistory.com/57

백준 js 11653: 소인수분해