[백준] 11653번 소인수분해_Python

1. 문제

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

 

2. 입력

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

 

3. 출력

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

 

 

4. 문제해결

N = int(input()) 
m = 2
while N!=1: 
  if N%m==0: 
    print(m) 
    N = N//m
  else:
    m += 1

소인수분해란 단어 뜻 그대로 수를 소인수로 분해하는 것을 의미한다.

소인수분해는 소인수로 분해해서 그것을 곱하면 N이 나오는 수이다. 그것을 인지하고 문제에 접근했다.

while문을 써서 N이 1일 때 끝내는 코드를 구현했다.

그래서 m을 2로 지정을 하고 2로 나눠 0이면 다시 N은 m이랑 나눠 반복을 해준다 만약에 2를 나누다가 0이 안되면 

m에 1씩 더해줘서 다시 나눠준다