[백준] 11653: 소인수분해 (javascript)

Link

11653번: 소인수분해

문제

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

입력 > 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.
출력 > N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

| 예제 입력

72

| 예제 출력

2
2
2
3
3

 

제출

const input = (
  process.platform == "linux"
    ? require("fs").readFileSync("/dev/stdin").toString()
    : `72`
).trim();

const N = Number(input);
let remainderNum = N;

let i = 2;

while (remainderNum !== 1) {
  if (remainderNum % i === 0) {
    remainderNum /= i;
    console.log(i);
    i = 2;
  } else {
    i++;
  }
}

 

풀이과정

첫 번째 제출 - 시간 초과

function searchPrimeNumber(N) {
  let primeNumbers = [];
  for (let i = 1; i <= N; i++) {
    let arr = [];

    if (i === 1) {
      continue;
    }

    for (let j = 2; j <= i; j++) {
      i % j === 0 && arr.push(j);
    }

    arr.length === 1 && primeNumbers.push(i);
  }

  return primeNumbers;
}

const input = (
  process.platform == "linux"
    ? require("fs").readFileSync("/dev/stdin").toString()
    : `72`
).trim();

const N = Number(input);
let remainderNum = N;

let i = 0;

while (remainderNum !== 1) {
  if (remainderNum % searchPrimeNumber(N)[i] === 0) {
    remainderNum /= searchPrimeNumber(N)[i];
    console.log(searchPrimeNumber(N)[i]);

    i = 0;
  } else {
    i++;
  }
}

🔼 이전 소수를 찾는 문제들에서 사용했던 코드를 함수로 만들어서 사용했다.

주어진 N을 N의 소수들로 나눠서 나누어 떨어지면 몫은 remainderNum에 저장하고, 해당되는 소수를 출력해주었다.

remainderNum이 1이되면 소인수 분해가 끝난다.

하지만 N의 범위가 1부터 10,000,000까지라 시간이 너무 오래 걸려 시간초과가 나왔다.

 

두 번째 제출 - 정답

const input = (
  process.platform == "linux"
    ? require("fs").readFileSync("/dev/stdin").toString()
    : `72`
).trim();

const N = Number(input);
let remainderNum = N;

let i = 2;

while (remainderNum !== 1) {
  if (remainderNum % i === 0) {
    remainderNum /= i;
    console.log(i);

    i = 2;
  } else {
    i++;
  }
}

🔼 굳이 소수를 구해서 나눠줄 필요가 없었다.

i가 소수가 아닌 어떤 수의 배수였다면, 이미 해당 수가 콘솔에 출력되었을 것이다.

예를 들어, remainderNum이 12로 나누어 떨어지는 수라면, 2로도 나누어 떨어지기 때문에 i는 소수만 출력될 것!!

---

Comment