소인수분해 계산기

이 온라인 소인수분해 계산기는 입력된 숫자의 모든 소인수를 빠르고 정확하게 찾아줍니다. 계산 결과는 일반 형식뿐만 아니라 지수 형식과 CSV 형식으로도 제공됩니다. 또한, 이 계산기를 활용하면 직관적인 소인수분해 트리를 생성할 수 있으며, 소인수 외에도 주어진 숫자의 모든 인수(약수)를 쉽게 구할 수 있습니다.

사용 방법

이 계산기로 소인수분해를 하려면 원하는 숫자를 입력하고 "계산하기" 버튼을 클릭하세요. 계산기가 즉시 해당 숫자의 소인수를 일반 형식, 지수 형식, CSV 형식의 목록으로 변환하여 보여줍니다.

소인수분해 트리를 시각적으로 확인하거나 주어진 숫자의 모든 인수를 찾는 추가 옵션도 제공됩니다. 원하는 기능의 체크박스를 선택하기만 하면 간단히 적용할 수 있습니다.

입력 값에 대한 제한

• 입력 값은 반드시 정수여야 하며, 소수(decimal)나 분수는 입력할 수 없습니다.
• 1보다 큰 양의 정수만 입력이 가능합니다.
• 숫자의 길이는 13자리를 초과할 수 없습니다(천 단위 구분 기호인 쉼표 제외). 즉, 입력값은 10,000,000,000,000(또는 10000000000000) 미만이어야 하며, 가능한 최대 입력 값은 9,999,999,999,999(또는 9999999999999)입니다.

소수와 합성수

소수(Prime number)란 1보다 큰 정수 중 1과 자기 자신만으로 나누어떨어지는 수를 말합니다. 다시 말해, 다른 정수들의 곱으로 표현할 수 없는 수입니다. 대표적인 소수로는 2, 3, 5, 7, 11, 13, 17 등이 있습니다(2는 유일한 짝수 소수이며, 이를 제외한 모든 소수는 홀수입니다).

위 목록에서 n번째 소수는 Prime[n]으로 표기할 수 있습니다. 예를 들어, Prime[1] = 2, Prime[2] = 3, Prime[3] = 5가 됩니다. 이 온라인 소인수분해 계산기는 n = 5000 이하의 모든 소수에 대해 해당 인덱스 n 값을 함께 제공합니다.

합성수(Composite number)는 1보다 큰 정수 중 다른 정수들의 곱으로 이루어진 수를 의미합니다. 예를 들어, 6은 3 × 2로 표현되므로 합성수입니다. 12 역시 12 = 6 × 2 = 3 × 2 × 2로 표현될 수 있는 합성수입니다.

숫자 인수분해

어떤 정수를 만들기 위해 곱해지는 수들을 '인수(약수)'라고 합니다. 앞서 살펴본 것처럼 3과 2는 6의 인수입니다. 또한 6은 1과 6의 곱(6 = 1 × 6)으로도 표현할 수 있으므로, 1과 6 역시 6의 인수입니다. 결과적으로 6의 모든 인수는 1, 2, 3, 6이 됩니다.

소수의 인수는 항상 1과 자기 자신뿐입니다. 예를 들어, 17의 인수는 1과 17밖에 없습니다.

소인수분해(Prime Factorization)는 주어진 숫자를 오직 소수들의 곱으로만 나타내는 과정입니다. 따라서 어떤 숫자를 소인수분해하는 것은 단순히 그 숫자의 모든 인수를 찾는 것과는 확연한 차이가 있습니다.

예를 들어, 12의 모든 인수를 나열하면 1, 2, 3, 4, 6, 12입니다.

반면, 12를 소인수분해한 결과는 12 = 2 × 2 × 3과 같이 나타납니다. 즉, 소인수분해 결과는 오직 소수 형태의 인수들로만 구성됩니다.

소인수분해 알고리즘

시행 나눗셈

가장 직관적인 소인수분해 방법인 '시행 나눗셈(Trial Division)'을 통해 36의 소인수를 찾는 과정을 알아봅시다. 소수들을 이미 알고 있다면, 주어진 숫자가 어떤 소수로 나누어떨어지는지 순차적으로 확인해 볼 수 있습니다. 가장 쉬운 방법은 제일 작은 소수인 2부터 나누기 시작하는 것입니다.

36 ÷ 2 = 18

나눗셈의 결과가 정수이므로, 2는 36의 소인수 중 하나임이 확인되었습니다. 하지만 18은 아직 소수가 아니기 때문에, 18이 2로 한 번 더 나누어떨어지는지 확인합니다.

18 ÷ 2 = 9

9 역시 정수입니다. 따라서 18은 2로 나누어떨어집니다.

다시 2로 나누어 봅시다. 9 ÷ 2 = 4.5로, 결과가 정수가 아닙니다. 이는 9가 더 이상 2로 나누어지지 않음을 의미합니다.

이제 그다음 소수인 3으로 나누어 봅니다. 9 ÷ 3 = 3. 결과가 정수이므로 나누어떨어졌습니다! 게다가 3은 그 자체로 소수이므로, 마침내 소인수분해 과정의 마지막 단계에 도달했습니다. 이제 최종 결과를 정리해 보겠습니다.

36 = 2 × 2 × 3 × 3

이것이 숫자의 소인수분해를 표현하는 일반적인 방식입니다. 이를 거듭제곱(지수) 형태로 요약하면 다음과 같이 작성할 수 있습니다.

36 = 2² × 3²

소인수분해 트리

소인수분해 과정은 나무가 가지를 뻗어나가는 형태인 "트리(Tree)" 구조로도 시각화할 수 있습니다. 36의 소인수분해 트리는 아래와 같은 모습입니다.

시행 나눗셈 (모든 인수)

때로는 숫자를 먼저 두 개의 더 작은 숫자(반드시 소수일 필요는 없음)의 곱으로 나눈 다음, 각각을 다시 소인수분해하는 것이 훨씬 더 효율적일 수 있습니다. 예를 들어 48의 소인수를 찾을 때, 48 = 6 × 8로 먼저 분해하는 것이 직관적입니다. 그런 다음 6을 소인수분해(6 = 2 × 3)하고, 8을 소인수분해(8 = 2 × 2 × 2)합니다. 이를 모두 합치면 최종적으로 48 = 2 × 2 × 2 × 2 × 3 = 2⁴ × 3¹이라는 결과를 얻게 됩니다.

산술의 기본 정리

1보다 큰 모든 양의 정수는 오직 단 한 가지의 고유한 소수들의 곱(소인수 집합)으로만 표현할 수 있습니다. 이를 수학에서는 '산술의 기본 정리(Fundamental Theorem of Arithmetic)' 또는 '소인수분해 정리'라고 부릅니다.

실생활 응용

소수는 현대 암호학 및 사이버 보안 분야에서 데이터를 암호화하고 해독하는 데 핵심적인 역할을 합니다. 앞서 살펴본 것처럼, 모든 숫자는 고유한 소수들의 곱으로 분해될 수 있습니다. 소수가 가진 이러한 독특한 수학적 성질이 암호화 시스템에 매우 유용하게 적용됩니다.

특히 암호학에서 유용한 점은, 매우 큰 숫자를 소인수분해하는 과정이 현대의 고성능 컴퓨터로도 천문학적인 시간이 걸리는 까다로운 작업이라는 사실입니다. 이 페이지의 계산기 역시 무한히 큰 숫자를 처리할 수 없는 이유가 바로 이 때문입니다.

소수를 활용한 암호화 기술의 핵심 원리는 비대칭성에 있습니다. 두 개의 거대한 소수를 곱해 더 큰 합성수를 만드는 것은 계산적으로 매우 간단합니다. 하지만 반대로, 그렇게 만들어진 거대한 합성수를 역으로 추적하여 원래의 두 소수로 분해해 내는 것은 굉장히 어렵습니다.

예를 들어 10자리 소수 두 개를 곱하여 자릿수가 훨씬 더 많은 엄청난 숫자를 만든다고 상상해 보세요. 그리고 그 거대한 숫자를 일일이 시행 나눗셈 방식을 통해 소인수분해한다고 생각해 보십시오...

이는 상상을 초월할 정도로 방대한 계산 과정이기 때문에, 현존하는 그 어떤 컴퓨터로도 합리적인 시간 내에 원래의 두 소수를 찾아내는 것은 불가능합니다. 다만, 훗날 양자 컴퓨터(Quantum Computer)가 상용화된다면 이러한 암호학적 패러다임도 미래에는 완전히 새로운 국면을 맞이할 수 있습니다.