백준 11653 번 문제 풀이 Python 파이썬 :소인수분해

#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.

코드편집/실행

N = int(input())
# 정수값을 받아서 정수형으로 변환 후 대입
n = 2 # 소수로 나누어줄 값.
while N != 1: # N 이 1이 아니면 계속
  if N % n == 0:
    print(n)
    N = N // n # 나누어 떨어지면 나누어 준다.
  else:
    n += 1 # 소인수가 아니면 n값을 증가시켜서 계속 진행