백준 11653번 문제풀이 - 소인수분해

백준 11653번 문제풀이 - 소인수분해

백준 11653번 문제

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

정수 N을 입력하면 소인수분해를 하는 문제이다.

소수를 구할 때처럼 분해하는 수를 점차 증가시키면서 출력되는 식으로 풀 수 있었다.

코딩

1.

2.

첫 번째 풀이의 경우 for문만을 사용하고 두 번째 풀이의 경우 for문안에 while문을 사용했다.

두 풀이에서 마지막 if문의 경우는 제곱근까지만 나눌 경우 제곱근보다 큰 N이 남아있을 수 있기 때문에

마지막을 출력하도록 했다.

결과

1.

2.

for문만을 사용했을 때와 for문 while문 두 가지를 썼을 때 속도차이를 느낄 수 있다.

느낀 점

소수가 암호학에 토대가 되는 만큼 일률적으로 구할 수 있는 공식이 없기 때문에 소인수분해 또한 반복문을 이용해서 일일이 다 구하는 과정이 필요했다. 이에 대한 이해를 더 할 수 있었다.

참고 : https://st-lab.tistory.com/152

from http://chobojonghyun.tistory.com/16 by ccl(A) rewrite - 2021-11-18 16:02:07