소인수분해

계산 비교

다운로드

이번 계산의 입력값과 결과, 그리고 비교하신 추가 계산이 모두 포함됩니다.

수를 소수 구성 요소로 분해하는 방법

1보다 큰 모든 자연수는 서로 곱해서 그 수가 되는 소수들의 유일한 집합으로 분해할 수 있습니다 — 바로 그 수의 소인수분해입니다. 자연수를 입력하면 이 계산기가 그 소인수분해를 즉시 구해 주며, 그 수 자체가 소수인지도 함께 알려줍니다.

계산식

산술의 기본 정리는 1보다 큰 모든 자연수 N이 인수를 쓰는 순서를 제외하면 정확히 하나의 소인수분해를 가진다는 것을 보장합니다:

\vA{N} = \vB{p_1}^{\vC{a_1}} \times \vB{p_2}^{\vC{a_2}} \times \cdots \times \vB{p_k}^{\vC{a_k}}

여기서 각 $\vB{p_i}$ 는 서로 다른 소수이고, 각 $\vC{a_i}$ 는 그 소수가 N을 나머지 없이 나누는 횟수입니다.

이 계산기는 시행 나눗셈을 사용해 그 소인수분해를 구합니다: 2부터 시작해 남은 값을 각 수가 나머지 없이 나누는지 반복적으로 확인하고, 나누어질 때마다 그 수로 나누며(몇 번 나누어지는지 세면서) 다음 후보로 넘어갑니다. 어떤 후보의 제곱이 남은 값을 넘어서면, 남아 있는 값은 그 자체로 소수일 수밖에 없습니다 — 그보다 작은 어떤 인수도 이미 발견되었을 것이기 때문입니다:

\text{만약 } \vD{d}^2 > \vE{\text{남은 값}}\text{이면, } \vE{\text{남은 값}}\text{은 소수입니다}

계산 예시

360의 소인수분해를 구해 보겠습니다:

360 ÷ 2 = 180, ÷ 2 = 90, ÷ 2 = 45 (2로 3번 나누어짐; 45는 홀수이므로 다음으로 넘어감).
45 ÷ 3 = 15, ÷ 3 = 5 (3으로 2번 나누어짐; 5는 3으로 더 나누어지지 않음).
5가 남고, 그 어떤 후보 수의 제곱도 5 이하가 되지 않으므로 5 자체가 소수입니다.
결과: 2³ × 3² × 5.

고려해야 할 주요 요소

모든 소인수분해는 유일합니다 — 이것이 바로 산술의 기본 정리가 보장하는 내용입니다. 어떤 방식으로 수를 분해하든, 그 소인수분해는 (인수를 쓰는 순서를 제외하면) 항상 동일하게 나오는데, 이것이 소인수분해가 정수론 전반에서 그토록 근본적인 구성 요소인 이유입니다.
소인수분해는 손으로 최대공약수나 최소공배수를 구하는 방법의 원리입니다. 두 수의 소인수분해를 직접 비교하면 최대공약수(공통으로 갖는 소인수를, 더 낮은 공통 지수로)와 최소공배수(모든 소인수를, 더 높은 지수로)를 바로 알 수 있습니다 — 그러한 특정 비교는 최대공약수/최소공배수 계산기를 참고하세요.
자릿수가 늘어날수록 큰 수를 인수분해하는 것은 계산적으로 훨씬 어려워지며, 이것이 일부 암호화 방식의 기반이 됩니다. 여기서 사용하는 시행 나눗셈은 사람이 직접 입력할 만한 크기의 수에는 잘 작동하지만, 수백 자리의 매우 큰 수를 인수분해하는 것은 강력한 컴퓨터로도 계산적으로 사실상 불가능할 수 있습니다 — 바로 이 어려움이 RSA 암호화의 보안성을 뒷받침합니다.
소수는 정확히 하나의 소인수를 가집니다: 자기 자신을 1제곱한 것입니다. 이것이 바로 이 계산기의 “이 수가 소수인가” 판단이 소인수분해 과정에서 자연스럽게 나오는 이유입니다 — 시행 나눗셈이 그 수의 제곱근보다 작은 인수를 전혀 찾지 못하면, 그 수는 자기 자신 외에 다른 인수분해를 갖지 않습니다.

흔한 실수

소인수분해를 전체 약수 목록과 혼동하는 것. 12의 약수는 1, 2, 3, 4, 6, 12이지만, 소인수분해는 2² × 3뿐입니다 — 소인수분해는 소수 구성 요소만 남기며, 나머지 없이 나누어지는 모든 수를 남기지 않습니다.
1을 소수로 취급하는 것. 정의상 소수는 정확히 두 개의 서로 다른 약수(1과 자기 자신)를 가집니다 — 1은 약수가 하나뿐이므로 소수도 합성수도 아니며, 어떤 소인수분해에도 결코 나타나지 않습니다.
반복되는 소인수를 놓치는 것. 8의 소인수분해는 단순히 “2”가 아니라 2³입니다 — 소수가 몇 번 나누어지는지를 잊으면 그 분해가 실제로 나타내는 수 자체가 바뀝니다.

알아두면 유용한 정보

한 수 자체의 약수가 아니라 두 수의 최대공약수나 최소공배수가 필요하신가요? 최대공약수·최소공배수 계산기은(는) 두 수의 소인수분해를 직접 비교합니다.
분수를 최소 형태로 약분하고 계신가요? 분수 계산기은(는) 이 계산기가 찾는 것과 동일한 공통 소인수를 사용합니다.
대신 매우 크거나 매우 작은 수를 다루고 계신가요? 과학적 표기법 계산기 은(는) 표준 표기법과 과학적 표기법 사이를 변환합니다.

출처: 시행 나눗셈.

자주 묻는 질문

소인수분해란 무엇인가요?

소인수분해는 자연수를 서로 곱하면 그 수가 되는 소수들로 분해하는 것입니다 - 1보다 큰 모든 자연수는 정확히 하나의 이러한 분해를 가집니다('산술의 기본 정리'). 예를 들어 12 = 2 × 2 × 3입니다.

어떤 수가 소수인지 어떻게 알 수 있나요?

소수는 1과 자기 자신 외에는 약수가 없는 수입니다. 입력한 수가 소수라면 이 계산기의 소인수분해 결과는 그 수 하나만(다른 인수 없이) 표시하며, 분석 섹션에서 이를 직접 알려줍니다.

인수분해할 수 있는 수의 크기에 한계가 있나요?

이 계산기는 시행 나눗셈을 사용하는데, 일반적인 계산기 사용 범위의 숫자에는 잘 작동하지만 (암호학에서 쓰이는 것과 같은) 매우 큰 수에서는 속도가 느려지며, 그런 경우에는 훨씬 더 정교한 알고리즘이 필요합니다.