소인수분해(11653번)

• 티어 : Bronze 1
• 정답여부 : 정답
• 알고리즘 유형 : 수학, 정수론, 소수 판정
• 시간 제한 : 1초

💡문제

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

💡입력

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

💡출력

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

💡문제요약

입력받은 숫자의 소인수분해를 구하여 출력하면 되는 문제

💡알고리즘 설계

✍️ 소인수분해란?

1보다 큰 자연수를 소인수(소수인 인수)들만의 곱으로 나타내는 것 또는 합성수를 소수의 곱으로 나타내는 방법

1. 숫자를 입력받음
2. 소인수분해를 담을 리스트를 만듬
3. 소인수분해를 구하기위해 2부터 N까지 for문을 돌림
4. 숫자를 i로 나눌때 0이면 그 숫자로 계속 나눠줌
5. 아닌 경우 i+1이 됨
6. soinsu 리스트를 k에 넣어 출력

💡작성코드

• python

N = int(input())
soinsu = []
for i in range(2, N+1):
    while N % i == 0:
        soinsu.append(i)
        N //= i   
for k in soinsu:
    print(k)

💡틀린 이유 or 수정할 부분

없음.

💡틀린 부분 수정 or 다른풀이

없음.

💡느낀점 or 기억할 정보

처음에 소인수분해가 뭔지 기억이 안 나서 헷갈렸다..ㅎㅎ 수학 개념이 정말 하나도 없는걸 느낌 ㅎㅎ