[BOJ] 백준 11653 소인수분해 (Swift)

문제

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

11653번: 소인수분해

풀이

소인수분해란, 소수들만의 곱으로 나타내는 것을 의미합니다.
에라토스테네스의 체를 사용해 소수들만으로 나누어 떨어지는지 확인해도 되지만..
그냥 2부터 나누어 떨어지는지 확인하고, 나누어 떨어지지 않으면 값을 올려주고 확인하고.. 반복하는 방법으로도 풀이할 수 있습니다.

n이 최대 1000만이기 때문에 시간안에 해결할 수 있지만, 시간을 줄일 수 있는 방법이 있을까요?

n = ab 라면, a와 b중 둘 중 하나는 $\sqrt{n}$ 보다 작은 성질이 있습니다.

따라서 n이 1000만에 가까운 소수여도, $\sqrt{10000000} = 3,163$인 2부터 약 3,163 까지 1씩 증가시켜서 확인해보고, 나누어 떨어지지 않는다면 소수이기 때문에, 바로 출력해주면 되겠네요!

1000만 -> 3,163 으로 연산의 횟수를 효율적으로 줄일 수 있게되었습니다.

소스코드

후기

단순하게 풀 수 있지만, 효율적으로 시간을 줄이는 방법에 대해서도 알아둬야겠다고 느꼈습니다.
백준에서도 56ms -> 12ms로 시간을 줄인 것을 확인했습니다.