소인수분해 계산기

이 온라인 소인수분해 계산기는 입력된 숫자의 모든 소인수를 찾습니다. 계산기는 일반 형식뿐만 아니라 지수 형식과 CSV 형식으로 소인수를 보여줍니다. 또한, 이 소인수분해 계산기는 소인수 트리를 생성하고 주어진 숫자의 모든 인수(소인수만이 아닌)를 찾을 수 있습니다.

사용 방법

이 계산기를 사용하여 숫자의 소인수를 찾으려면, 주어진 숫자를 입력하고 ""계산하기""를 누르세요. 계산기는 숫자의 소인수를 일반 형식, 지수 형식, CSV 형식의 목록으로 반환합니다.

인수분해 트리를 생성하거나 주어진 숫자의 모든 인수를 찾는 옵션도 있습니다. 이 두 옵션은 해당하는 상자를 선택하여 선택할 수 있습니다.

입력 값에 대한 제한

• 입력 값은 정수여야 합니다; 소수와 분수는 허용되지 않습니다.
• 1보다 큰 양의 정수만 입력으로 사용할 수 있습니다.
• 숫자의 길이는 13자리를 초과할 수 없습니다(천 단위를 구분하는 쉼표 없이). 즉, 입력 숫자의 값은 10,000,000,000,000 또는 10000000000000보다 작아야 합니다. 최대 입력 값은 따라서 9,999,999,999,999 또는 9999999999999입니다.

소수와 합성수

소수는 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을 보여줍니다.

합성수는 1보다 큰 정수로, 다른 정수를 곱하여 만들 수 있는 수입니다. 예를 들어, 6은 합성수입니다. 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입니다.

소인수분해는 주어진 숫자를 만들 수 있는 모든 소수를 찾는 과정입니다. 숫자의 소인수분해는 그 숫자의 모든 인수를 찾는 것과 다릅니다.

예를 들어, 12의 모든 인수는 1, 2, 3, 4, 6, 12입니다. 이 인수들은 목록으로 작성됩니다.

반면에 12의 소인수분해는 다음과 같이 보일 것입니다: 12 = 2 × 2 × 3. 소인수분해에서는 소수 형태로만 결과가 나옵니다.

소인수분해 알고리즘

시행 나눗셈

가장 직관적인 소인수분해 방법인 시행 나눗셈 방법을 예시를 들어 살펴보고, 36의 소인수를 찾아봅시다. 모든 소수를 알고 있으므로, 주어진 숫자가 그 중 어느 것으로도 나눌 수 있는지 확인할 수 있습니다. 가장 쉬운 방법은 가장 작은 소수인 2부터 시작하는 것입니다:

36 ÷ 2 = 18

이 나눗셈의 결과는 정수입니다. 따라서, 2는 36의 소인수 중 하나입니다. 그러나 18은 아직 소수가 아니므로, 18이 2로 나눌 수 있는지 계속 확인합니다:

18 ÷ 2 = 9

9도 정수입니다. 따라서, 18은 2로 나눌 수 있습니다.

다시 시도해 봅시다: 9 ÷ 2 = 4.5. 이것은 정수가 아닙니다. 따라서, 9는 2로 나눌 수 없습니다.

다음 소수인 3을 시도해 봅시다. 9 ÷ 3 = 3. 이것은 정수이므로, 성공했습니다! 게다가 3은 이미 소수이므로, 과정의 마지막 단계에 도달했습니다! 이제 최종 답을 적어야 합니다:

36 = 2 × 2 × 3 × 3

이것은 숫자의 소인수분해를 적는 일반적인 방법입니다. 지수를 사용하여 다음과 같이 쓸 수도 있습니다:

36 = 2² × 3²

소인수분해 트리

소인수분해 과정은 ""트리""로도 표현될 수 있습니다. 36의 소인수분해 트리는 다음과 같습니다:

시행 나눗셈 (모든 인수)

때때로, 숫자를 먼저 두 개의 다른 (소수가 아닌) 숫자의 곱으로 표현한 다음 그들의 소인수를 찾으면 소인수분해 과정이 더 쉬워집니다. 예를 들어, 48의 소인수를 찾아봅시다. 48 = 6 × 8로 시작하는 것이 더 쉽습니다. 그 다음에는 6의 소인수를 찾아야 합니다: 6 = 2 × 3, 그리고 8: 8 = 2 × 2 × 2. 마지막으로, 48 = 2 × 2 × 2 × 2 × 3 = 2⁴ × 3¹이 됩니다.

산술의 기본 정리

1보다 큰 어떤 양의 정수도 고유한 소인수 집합으로 만들어질 수 있습니다. 이 정리는 때때로 소인수분해 정리라고 불립니다.

실생활 응용

소수는 암호화 및 사이버 보안에서 메시지를 암호화하고 해독하는 데 사용됩니다. 어떤 숫자도 소수 집합의 곱으로 표현될 수 있으며, 이 집합은 고유하다는 것을 이미 알고 있습니다. 소수의 이러한 특성이 암호화에 편리하게 사용됩니다.

더욱 편리한 것은 매우 큰 숫자의 소인수를 찾는 것이 현대 컴퓨터에도 매우 시간이 많이 걸리는 작업이라는 것입니다. 그래서 이 페이지의 계산기가 무한히 큰 숫자로 작동할 수 없는 이유입니다.

소수를 사용한 암호화의 핵심 원리는 두 개의 큰 소수를 취해 훨씬 더 큰 합성수를 만드는 것이 상대적으로 쉽다는 것입니다. 그러나 그 최종 숫자를 원래의 소수로 분해하는 것은 굉장히 어렵습니다.

10자리 소수 두 개를 취해 더 많은 자릿수를 가진 숫자를 만드는 것을 상상해보세요. 이제 그 숫자의 소인수분해를 시행 나눗셈으로 하는 과정을 상상해보세요...

이것은 너무 긴 과정이어서 현재 어떤 컴퓨터도 주어진 문제에서 두 초기 소수를 합리적인 시간 내에 찾을 수 없습니다. 그러나 양자 컴퓨터의 발달로 미래에는 이 상황이 변할 수 있습니다.