🐷전동준(Jeon DongJun)

Go with the flow

[BOJ/백준-Python]11653번 - 소인수분해

11653번 - 소인수분해

문제

정수 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

해결할 방법을 생각해보자.💡

우선 채점이 생각보다 오래걸리는 것에 당황했다…;;

image

결과가 1%씩 올라갈 때마다 틀렸다거나 시간초과가 뜰까봐 조마조마했다.

어쨌든 문제는 잘 풀었으니 다행이다!

자, 우선 내가 알고 있는 소인수분해의 의미?개념?.. 은 다음과 같다.

모든 양의 정수는 소수들로 이루어져있기에, 소수들의 곱으로 표현할 수있다.

이제 문제 풀이를 한번 적어보겠다.

처음에 양의 정수(자연수) N을 받아주자.

N = int(input())

그리고 1은 소수가 아니다. 2부터 소수가 시작되기 때문에 소수 n을 선언해주자.

n = 2

이제 while문을 사용해 줄 것이다. 우리가 받은 자연수N이 1과 같거나 작아지면 반복이 멈춘다.

while N > 1:

만약에 받은 수 N이 소수 n(2로 시작하는)로 딱 나눠지지 않는다면, n에 1을 추가한다.

	if N % n != 0:
        n += 1

그게 아니라면(나누어 떨어진다면), 현재 소수 n을 출력하고, 기존의 자연수 N을 소수 n으로 나눈 값으로 바꿔주고, n을 2로 다시 초기화 시켜주면된다.

이러면 문제 조건과 같이 N이 1로 입력되었을 경우에는 자연스럽게 아무것도 출력이 되지 않아서 문제를 해결할 수 있다!

코드💻

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

해결 로그

문제 푼 날짜 체크
2022-06-11 ✔
   
   
   
   

2022

[web]jQuery 복습 3

1 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]jQuery 복습 2

13 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]jQuery 복습 1

14 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]JavaScript 정리4

5 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]JavaScript 정리3

10 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]JavaScript 정리2

7 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]JavaScript 정리1

8 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]CSS 기초 정리

11 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[web]HTML 기초 정리

8 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

[Pandas]pandas 연습

3 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

맨 위로 이동 ↑

2021

[Python기초]module

1 분 소요

[Noitce] 고쳐야하거나 틀린 것이 있으면 말씀해주세요!

맨 위로 이동 ↑