소인수분해 계산기 (소인수·인수 나무)

결과

소인수

2 x 2 x 5 x 5

해당 수의 소수 분해

소수 분해 (지수 형태)	2^2 x 5^2
소인수 CSV 목록	2, 2, 5, 5
서로 다른 소인수의 개수	2
전체 소인수 개수 (중복 포함)	4
소수 인덱스 Prime[n]	2 = Prime[1], 5 = Prime[3]

소인수분해란?

소인수분해(정수 분해 또는 소수 분해라고도 합니다)는 양의 정수를 곱해서 그 수를 만들어내는 소수들로 쪼개는 과정입니다. 산술의 기본 정리에 따르면, 1보다 큰 모든 정수는 순서를 무시할 때 단 하나의 소인수분해만 가집니다. 이 계산기는 2부터 약 10조(13자리) 미만까지의 모든 자연수를 소인수분해하여 네 가지 방식으로 보여줍니다. 곱셈식, 지수 형태, CSV 목록, 그리고 선택적으로 인수 나무입니다.

합성수가 소수 구성 요소로 나뉘는 모습 — 모든 정수는 유일한 소인수 집합으로 분해된다.

사용 방법

입력란에 1보다 큰 양의 정수를 입력하고 실행하세요. 시각적인 분해 과정을 보고 싶다면 "인수 나무 만들기"를 체크하면 됩니다. 결과로는 풀어 쓴 소인수(예: $2 \times 2 \times 5 \times 5$), 간결한 지수 형태($2^2 \times 5^2$), 쉼표로 구분된 목록, 서로 다른 소수의 개수, 중복도를 포함한 전체 소인수 개수, 그리고 처음 5000개 소수에 속하는 인수의 소수 인덱스 $\text{Prime}[n]$가 함께 표시됩니다.

공식과 알고리즘

이 계산기는 시험 나눗셈(trial division) 방식을 사용합니다. 먼저 2로 나눌 수 있는 인수를 모두 제거한 뒤, 나누는 수의 제곱이 남은 값보다 크지 않은 동안 3, 5, 7, ... 같은 홀수 약수를 차례로 시험합니다. 어떤 약수로 딱 떨어지면 그 약수를 기록하고 나눕니다. 마지막에 1보다 큰 값이 남으면 그 자체가 하나의 소인수입니다. 제곱근까지만 검사해도 되는 이유는, 모든 합성수는 반드시 자신의 제곱근 이하의 인수를 가지기 때문입니다.

$$\text{Number} = p_1^{e_1} \times p_2^{e_2} \times \cdots \times p_k^{e_k}$$

예제 풀이: n = 100

$$100 / 2 = 50, \quad 50 / 2 = 25$$ 이므로 2가 두 개입니다. 그다음 25는 3으로는 나누어지지 않지만 5로는 나누어집니다. $$25 / 5 = 5, \quad 5 / 5 = 1$$ 이므로 5가 두 개입니다. 따라서 인수는 2, 2, 5, 5 입니다. 곱셈식으로는 $2 \times 2 \times 5 \times 5$, 지수 형태로는 $2^2 \times 5^2$ 입니다. 서로 다른 소수는 2개, 전체 소인수는 4개입니다. 검산: $$2 \times 2 \times 5 \times 5 = 100$$ 소수 인덱스는 $2 = \text{Prime}[1]$, $5 = \text{Prime}[3]$ 입니다.