백준 11653 번 문제 풀이 C++ :소인수분해

#66. 백준 11653번 문제 풀이: 소인수분해

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성 입력: 정수 N (1 ≤ N ≤ 10,000,000) 출력: N의 소인수분해 결과를 한 줄에 하나씩 작은 수부터 출력. N이 1인 경우 출력하지 않음.

입력/출력

--입력--
72
--출력--
2
2
2
3
3
--입력--
3
--출력--
3
--입력--
6
--출력--
2
3
--입력--
9991
--출력--
97
103

문제풀이+해설

소인수 분해는 1보다 큰 자연수를 소인수(소수인 인수)들만의 곱으로 나타내는 것이다.
예를 들어 12의 경우 2x2x3 이 된다.

문제를 해결하는 방법은 작은 소인수부터 출력하라고 했으니, 2부터 나누어 떨어지는 수들을 출력해 주면 된다.
주의 할것은 예를 들어 2로 나누어 떨어지더라도, 3으로 가지 않고 나누어 떨어지면 계속 나누어야 한다.

--
루프 (N 이 1보다 클때까지 n=2 부터 반복)
  N%n 이 0이면 소수:n출력
  그렇치 않으면 n을 +1 하고 루프계속
루프 끝
--

code sol.

코드편집/실행

#include <iostream>
using namespace std;

int main() {
  int n, N;
  cin >> N; // 정수값을 받아서 정수형으로 변환 후 대입
  n = 2 ; // 소수로 나누어줄 값.
  while(N != 1) { // N 이 1보다 크면 계속
    if(N % n == 0) { // 나누어 떨어지면..소인수
      cout << n << endl; // 소인수 출력
      N = N / n; // 나누어 떨어지면 나누어 준다.
    } else n++; // 소인수가 아니면 n값을 증가시켜서 계속 진행
  }
  return 0;
}