문제
1보다 큰 모든 정수는 인수의 순서를 무시하면 소수의 곱으로 나타내는 방법이 단 하나뿐입니다(산술의 기본 정리). 예를 들어 360 = 2 × 2 × 2 × 3 × 3 × 5입니다. 이 목록을 구하는 것을 소인수분해라고 합니다.
prime_factorization(n) 함수를 구현하세요.
n은 최대 10^12까지 커질 수 있으므로, 대표적인 방법은 작은 수부터 차례로 나누어 보는 시험 나눗셈(trial division)입니다. 2로 나누어떨어지는 동안 계속 나누고, 그다음 3으로 나누는 식입니다. d × d가 n에서 아직 남은 부분 이하인 동안만 d를 시도하면 되고, 마지막에 1보다 큰 값이 남으면 그 값 자체가 소수입니다. 이렇게 하면 n이 큰 소수이거나 큰 소수 두 개의 곱이더라도 작업량이 약 √n ≈ 10^6단계에 그칩니다.
입력
n: 소인수분해할 수입니다.
출력
n의 소인수를 오름차순으로 반환합니다. 각 소수는 n을 나누는 횟수만큼 반복해서, 리스트의 원소를 모두 곱하면 n이 되도록 합니다. n = 1이면 빈 리스트를 반환합니다. n이 소수이면 리스트에는 n 하나만 들어갑니다.
제약 조건
1 ≤ n ≤ 10^12
예시
입력:
n = 360
예상 출력:
expected = [2, 2, 2, 3, 3, 5]
입력:
long long n = 360;
예상 출력:
std::vector<long long> expected = {2, 2, 2, 3, 3, 5};
입력:
long n = 360;
예상 출력:
long[] expected = new long[] {2, 2, 2, 3, 3, 5};
설명
360 = 2 × 180 = 2 × 2 × 90 = 2 × 2 × 2 × 45 = 2 × 2 × 2 × 3 × 15 = 2 × 2 × 2 × 3 × 3 × 5이므로 답은 [2, 2, 2, 3, 3, 5]입니다.
입력:
n = 97
예상 출력:
expected = [97]
입력:
long long n = 97;
예상 출력:
std::vector<long long> expected = {97};
입력:
long n = 97;
예상 출력:
long[] expected = new long[] {97};
설명
√97 ≈ 9.8 이하의 소수(2, 3, 5, 7)로는 97이 나누어떨어지지 않으므로 97은 소수이고, 답은 [97]입니다.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
2로 나누어떨어지는 동안 계속 나누고, 그다음 3, 5, 7, … 순서로 넘어가세요.
힌트 2
인수를 찾을 때마다 n을 줄이고, d × d를 줄어든 n과 비교하세요.
힌트 3
반복문이 끝난 뒤 1보다 큰 값이 남아 있으면 그것이 가장 큰 소인수입니다.
예상 복잡도
시간 O(√n), 결과를 담는 추가 공간 O(log n)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.