[백준] 11653번 - 소인수분해 (node.js)

 

 

 

 

[백준] 11653번 - 소인수분해 (node.js)

 

 

링크

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

 

 

 

문제

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

 

 

 

입력

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

 

 

 

출력

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

 

 

 

예제

입력 1

72

 

출력 1 

2
2
2
3
3

입력 2 

9991

 

출력 2 

97
103

 

 

 

답안

답 1

const fs = require("fs");
const str = fs.readFileSync("input.txt").toString().trim();
let num = parseInt(str);

const arr = [];
for (let i = 2; i <= num; i++) {
    while (num % i === 0) {
        console.log(i);
        arr.push(i);
        num = num / i;
    }
	if (num === 1) break;
}

console.log(arr.join("\n"));

 

답 2

const fs = require("fs");
const str = fs.readFileSync("input.txt").toString().trim();
let num = parseInt(str);

const arr = [];
소인수분해(Number(N));

function 소인수분해(num) {
	if (num === 1) return;
	let i = 2;

    while (num % i !== 0) {
        i++;
    }
	arr.push(i);

	소인수분해(num / i);
}

console.log(arr.join("\n"));

 

 

 

풀이

소인수분해?

소인수분해는 자연수를 그 수를 나눌 수 있는 소수(prime numbers)들의 곱으로 나타내는 것을 말합니다.

이 과정에서 해당 자연수는 자신보다 작거나 같은 소수들로만 나누어집니다.

소인수분해를 통해, 어떤 수가 어떤 소수들의 곱으로 이루어져 있는지를 명확하게 알 수 있습니다.

예를 들어, 숫자 60의 소인수분해는 다음과 같이 이루어집니다

60 = 2 x 2 × 3 × 5;
60 = 2 x 2 × 3 × 5 여기서 2, 3, 5는 모두 소수입니다.

 

소수들의 곱으로 나타내는 거래서

소수를 구하고, 그 소수들을 루프해서 구하고 그랬는데,,

그냥 첨부터 num이 1이 될때까지 구하면 되는 문제였다.

 

 

 

 

 

참조!

https://velog.io/@gusdh2/JS%EB%B0%B1%EC%A4%80-11653%EB%B2%88-%EC%86%8C%EC%9D%B8%EC%88%98%EB%B6%84%ED%95%B4-%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8node.jsjavascript%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8

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

 

https://sunflo0524.tistory.com/68

[백준 / nodejs] 11653번 : 소인수분해