[백준 알고리즘] 11653번 : 소인수분해, c++

https://www.acmicpc.net/problem/11653

11653번: 소인수분해

c++로 백준 11653번 문제를 풀어보겠다.

 

 

 

 

 

문제

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

입력

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

출력

N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

예제 입력 1 복사

72

예제 출력 1 복사

2
2
2
3
3

 

 

 

 

 

 

<문제 풀이>

 

처음에 작성한 코드는 다음과 같다.

visual studio에선 문제없이 돌아 원하는 값을 출력했지만, 백준 알고리즘 사이트에서는 '시간 초과' 라고 떴다.

코드가 도는데 뭔가 시간이 오래 걸린다는 뜻이었다.

 

2부터 해당 숫자가 소수인지 판별한 후, N의 소인수면 출력해주는 코드였다.

 

 

 

 

하지만 생각해보니, 굳이 소수인지 판별하는 코드를 거치지 않아도 가능했다.

내가 처음에 소수인지 판별하는 코드를 작성한 이유는, 어떤 수의 소인수란 결국 다른 수로는 절대 나누어 떨어지지 않는 '소수'이기 때문이었다.

먼저 소수인지 판단하고, 소수라면 N과 나누어 떨어지는지 판별해 소인수를 얻어낸 것이다.

 

하지만 어차피 숫자는 2부터 차례로 올라가니 굳이 소수인지 판별하지 않아도 되는 것이다. 

나는 4와 같은 숫자도 완벽한 소인수 2, 2가 아닌 4로 취급할까봐 소수인지 판별하는 코드를 사용했던 것인데, 어차피 숫자는 2부터 차례로 올라가니 그럴 일이 절대 없는 것이었다.

 

 

 

따라서 내가 최종적으로 작성한 코드는 다음과 같다.

 

 

1. N을 선언한 후 입력받는다.

2. while 문을 반복한다.

 

- while 반복문 코드 내용 -

만약 N이 1이라면 반복문을 종료한다.

만약 i(소인수를 계산하는 수)가 10000000이라면 반복문을 종료한다.

만약 N이 sum 과 같다면 반복문을 종료한다.

만약 N이 i로 나눈 나머지가 0이라면 i를 출력하고, sum에 곱해준 후 N의 값을 재설정한다.

만약 N이 i로 나눈 나머지가 0이 아니라면 i를 하나 증가시킨다.