목록11653 (1)

Altiora Petamus

소인수분해

11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 🤔생각해보기 n을 i 로 나눠보고 나머지가 0 이라면 출력, n //= i 를 사용하여 n을 몫으로 재설정 n이 i로 나누어지지 않는다면 i += 1 i^2가 n과 같아질 때까지 실행 만약 n = 10이라면, 2 로 나누어지고 n = 5 가 된다. 5는 소수이므로 i는 증가만 하다가 5가 되면서 루프를 빠져나오게 되고 결과가 2와 5만 출력되게 된다. 5는 소수이므로 ⇒ 소수를 판별하는 과정은 제곱근을 활용한다. 자세히 생각해보니 i와 n이 같아질 때까지 검사하는 것은 시간복잡도만 증가시킬 것 같았다. 애초에 루프를 i의 제곱이 n과 같아질 때까지만 실행시키면 된다. 성공 코드 n ..
1day-1algorithm 2021. 5. 29. 02:43
이전 Prev 1 Next 다음