모든 챌린지
보통 0명 해결 정답률 0%

소인수분해

수를 소인수로 분해해 작은 것부터 큰 것 순서로, 중복을 포함해 나열합니다.

배우게 될 내용

  • 각 인수를 나타나는 횟수만큼 나누어 낼 수 있습니다
  • d × d가 남은 값보다 커지면 시험 나눗셈을 멈출 수 있습니다
  • 마지막에 남은 1보다 큰 값이 소인수임을 알 수 있습니다

문제

원문 보기 (영어)

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

예시

예시 1
입력:
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]입니다.

예시 2
입력:
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에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.

코더마다 가장 좋은 통과 풀이입니다. 더 빠르고, 메모리를 덜 쓰고, 평가가 좋은 풀이가 위에 옵니다.

아직 통과한 풀이가 없습니다. 풀어서 1위를 차지하세요.

다른 사람의 풀이 보기

커뮤니티 솔루션

아직 공개된 풀이가 없습니다. 문제를 풀고 첫 풀이를 공유하세요.