소인수분해 계산기

360 = 2^3 * 3^2 * 5; Ω(360) = 3 + 2 + 1 = 6; d(360) = (3+1) * (2+1) * (1+1) = 24

n

쪼개는 대상인 수이고 1에서 1000000까지의 자연수입니다. 이 범위는 수론 모듈이 처음부터 쓰는 값이라 약수 페이지와 정확히 같고, 두 페이지를 오가는 독자는 같은 경계를 만납니다. 소수점이 있는 입력은 반올림하지 않고 거부하며, 0과 음수도 거부합니다. 소인수분해는 양의 자연수에 대한 진술이기 때문입니다

p

소인수이고 n을 나머지 없이 나누는 소수(素數)입니다. 이 페이지는 작은 소수부터 차례로 나눠 보며 찾으므로 가장 작은 소수가 언제나 먼저 빠져나오고, 인쇄되는 분해식은 늘 작은 소수에서 큰 소수로 흐릅니다. 360에서 소수(素數)는 2, 3, 5이고 다른 소수(素數)는 하나도 360을 나누지 않습니다

e

어떤 소수가 곱 안에 몇 번 들어가는지를 나타내는 지수입니다. 360은 2 × 2 × 2 × 3 × 3 × 5이므로 2가 세 번, 3이 두 번 나옵니다. 한 번만 나오는 소수(素數)에는 지수를 아예 인쇄하지 않습니다. 360의 5는 5^1이 아니라 그냥 5로 적히는데, 이것이 통상적인 관례이고 짧은 분해식을 읽기 좋게 지켜 줍니다

2^3 * 3^2 * 5

기본 입력인 360의 분해식을 인쇄한 모습입니다. 캐럿은 지수를, 별표는 곱셈을 뜻해서 이 문자열은 평범한 텍스트 칸이나 검색창에 그대로 붙여 넣어도 살아남습니다. 1보다 큰 자연수마다 이런 식이 꼭 하나씩 있다는 것이 이 식을 인쇄할 값어치로 만듭니다. 산술의 기본 정리라고 부르는 이 사실 덕분에 360이 다른 소수(素數)들의 곱으로도 적힐 수 있는 일은 없습니다

Ω(360) = 3 + 2 + 1 = 6

되풀이를 포함한 소인수 개수이고, 2가 셋, 3이 둘, 5가 하나로 모두 여섯입니다. 360은 소수(素數) 셋으로 이루어진 것처럼 느껴지므로 이 값이 사람을 놀라게 합니다. 구하는 방법은 서로 다른 소수(素數)의 개수가 아니라 지수를 더하는 것이고, 지수가 1보다 큰 소수(素數)가 하나라도 있으면 두 답이 갈립니다

d(360) = (3+1) * (2+1) * (1+1) = 24

양의 약수 개수이고, 같은 지수들에 각각 1을 더한 뒤 곱해서 구합니다. 목록은 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360이고 모두 스물네 개입니다. 이것은 바로 위와 다른 질문입니다. 360을 만드는 소수(素數)가 아니라 360을 나누는 수를 세고 있습니다

소인수분해가 필요한 것은 질문이 수의 크기가 아니라 곱셈 구조에 관한 것일 때입니다. 분수나 제곱근을 간단히 하는 일이 가장 흔한 경우입니다. 72의 제곱근이 6√2로 정리되는 것은 72 = 2³ × 3²이기 때문이고, 각 소수(素數)의 지수가 그 소수(素數)를 근호 밖으로 얼마나 꺼낼 수 있는지를 알려 줍니다. 두 수의 최대공약수나 최소공배수를 구하는 일도 같은 분해를 수마다 한 번씩 하는 것입니다. 공통인 소수(素數)를 작은 지수로 택하면 앞의 것이 되고, 모든 소수(素數)를 큰 지수로 택하면 뒤의 것이 됩니다. 어떤 수가 다른 수를 나누는지는 그 수의 소수(素數)와 지수가 상대에게 모두 있는지로 판정되므로 나누어떨어짐도 같은 방식으로 답합니다. 수론에서는 어떤 수가 소수(素數)인지, 약수가 몇 개인지, 완전제곱수인지(모든 지수가 짝수), 완전세제곱수인지도 분해식 하나로 정리됩니다. 이 방법의 한계도 알아 둘 만합니다. 시험 나눗셈은 100만에서는 빠르지만 백 자리 수에서는 희망이 없고, 그 벌어짐이 바로 공개키 암호가 세워진 자리입니다. 어떤 수를 나누는 수가 궁금한 것이 아니라 어떤 소수(素數)로 만들어졌는지가 궁금하면 약수 페이지가 목록을 보여 주고, 그 수가 애초에 소수(素數)인지가 궁금하면 소수 판별기가 그것에 바로 답합니다. 이 소인수분해 계산기가 필요한 순간에는 이 페이지가 지수 꼴과 두 개수를 함께 인쇄합니다.

1. 기본값인 360

   1. 360은 짝수이므로 2로 나눕니다. 360 / 2 = 180, 180 / 2 = 90, 90 / 2 = 45이고 모두 세 번입니다
   2. 45는 짝수가 아니므로 다음 소수인 3으로 나눕니다. 45 / 3 = 15, 15 / 3 = 5이고 두 번입니다
   3. 5는 소수(素數)이므로 분해식은 2 × 2 × 2 × 3 × 3 × 5이고 2^3 * 3^2 * 5로 적습니다
   4. 되풀이를 포함해 소인수를 셉니다. 3 + 2 + 1 = 6입니다
   5. 지수에서 약수 개수를 구합니다. (3 + 1) × (2 + 1) × (1 + 1) = 4 × 3 × 2 = 24입니다

   기본 입력이고, 두 개수를 왜 함께 인쇄하는지 보여 주는 자리입니다. 6과 24가 나란히 있으면 두 값이 같기를 기대한 독자는 하나가 고장 났다고 생각합니다. 그렇지 않습니다. 6은 되풀이를 하나도 빠뜨리지 않고 셌을 때 이 수가 몇 조각의 소수(素數)로 이루어졌는지이고, 24는 이 수를 나누는 수가 몇 개인지입니다. 둘 사이의 벌어짐은 지수에서 나옵니다. 소수(素數)가 한 번 더 반복될 때마다 약수 개수는 배로 늘지만 조각의 수는 하나만 늘어납니다. 어느 쪽이든 손으로 확인하면 짧고, 둘 다 확인하면 어느 쪽이 어느 쪽인지 기억하게 됩니다.

2. 차이를 보여 주는 작은 경우: 12

   1. 12 / 2 = 6이고 6 / 2 = 3이므로 2가 두 번 나옵니다
   2. 3은 소수(素數)이므로 분해식은 2^2 * 3입니다
   3. 되풀이를 포함해 소인수를 셉니다. 2 + 1 = 3이고 이는 2, 2, 3입니다
   4. 약수를 나열합니다. 1, 2, 3, 4, 6, 12로 여섯 개입니다
   5. 요령으로 확인합니다. (2 + 1) × (1 + 1) = 3 × 2 = 6이고 목록과 맞습니다

   이 페이지가 겨냥한 혼동을 가장 또렷하게 보여 주는 작은 예입니다. 두 값이 모두 손으로 몇 초 만에 확인할 만큼 작기 때문입니다. 12는 소수(素數) 세 개, 곧 2, 2, 3으로 만들어졌고 여섯 개의 수가 그것을 나눕니다. 출력을 약수 3개로 읽든 소인수 6개로 읽든 그럴듯하게 들리지만 둘 다 틀렸습니다. 약수 목록은 여섯이 짝수인 이유도 보여 줍니다. 1은 12와, 2는 6과, 3은 4와 짝을 이룹니다. 12는 완전제곱수가 아니라서 자기 자신과 짝을 이루는 약수가 없고, 그래서 개수가 짝수입니다.

3. 지수를 인쇄하지 않는 경우: 97

   1. 97은 2로도 3으로도 5로도 7로도 나누어떨어지지 않고, 10보다 큰 소수(素數)는 제곱이 97을 넘으므로 더 볼 필요가 없습니다
   2. 따라서 분해식은 97 그 자체이고, 한 번만 나오는 소수(素數)이므로 지수를 인쇄하지 않습니다
   3. 되풀이를 포함한 소인수 개수는 1입니다
   4. 약수는 1과 97 둘뿐이므로 약수 개수는 2입니다

   소수(素數)가 들어왔을 때 두 개수가 각각 최소값에 머문다는 것을 보여 주는 경우입니다. 분해식이 97^1이 아니라 97로 인쇄되는 것도 여기서 확인됩니다. 지수가 1일 때 지수를 적는 것은 소음일 뿐이고, 소수(素數)로만 이루어진 수, 곧 제곱인수가 없는 수는 캐럿이 하나도 없는 평범한 곱으로 읽힙니다. 약수 개수가 2라는 것은 1과 자기 자신만이 97을 나눈다는 뜻이고, 그 정의가 곧 소수(素數)의 정의입니다. 두 개수의 최소값이 각각 1과 2라는 사실도 여기서 한 번에 보입니다.

4. 따로 정해 두어야 하는 경우: 1

   1. 1은 어떤 소수(素數)로도 나누어떨어지지 않습니다. 2로 나누든 3으로 나누든 분수가 남습니다
   2. 그래서 소인수가 없고 그 개수는 0입니다
   3. 1을 나누는 양의 자연수는 1뿐이므로 약수 개수는 1입니다
   4. 분해식은 빈 칸이 아니라 숫자 1 하나로 인쇄됩니다

   유도되지 않고 정해 두어야 하는 경우이고, 결정은 1을 인쇄하는 쪽입니다. 분해식을 빈칸으로 두면 계산에 실패한 것처럼 읽히는데, 결과 패널이 절대 그렇게 보여서는 안 됩니다. 두 개수는 그대로 따라 나옵니다. 소수(素數)는 하나도 없고 약수는 하나입니다. 1은 소수(素數)도 합성수도 아닙니다. 곱셈의 항등원이고, 곱해도 아무것도 바뀌지 않는 수입니다. 이 페이지는 그것을 다른 것인 척하지 않습니다. 입력 범위가 1에서 시작하므로 거부하지 않고 받아들이는데, 자기 범위의 맨 아래 값을 거부하는 쪽이 설명하기 더 이상했을 것입니다.

입력은 1에서 1000000까지의 자연수여야 합니다. 0은 거부합니다. 모든 소수(素數)가 0을 나누므로 곱이 무한히 길어져야 하기 때문입니다. 음수도 비슷한 이유로 거부합니다. 소수(素數)들이 음수도 나누기는 하지만 부호를 따로 들고 다녀야 하고, 분해가 하나뿐이라는 정리는 양수에 대한 진술이기 때문입니다. 소수점이 있는 입력은 반올림하지 않고 거부합니다. 반올림하면 다른 수에 대한 질문에 조용히 답하게 되기 때문입니다. 100만이라는 상한은 공유 수론 모듈에서 왔고 정확성이 아니라 비용의 문제입니다. 제곱근까지의 소수(素數)로 나눠 보는 방법은 100만에서는 빠르고 스무 자리 수에서는 희망이 없습니다. 이것은 이 방법의 진짜 경계이고, 공개키 암호를 성립시키는 것도 같은 경계입니다. 이 페이지는 분해식과 두 개수를 보고하고 그 밖에는 하지 않습니다. 약수를 직접 나열하지 않고, 여러 수의 최대공약수나 최소공배수를 구하지 않으며, 근호나 분수를 정리하지도 않습니다. 지수가 1일 때는 인쇄하지 않으므로 한 번만 나오는 소수(素數)는 지수 없이 맨몸으로 보이고, 곱셈 기호는 처음부터 끝까지 별표라서 출력이 순수 ASCII이고 천 단위 구분 기호도 없습니다. 마지막으로 아래 참고표는 입력을 따라가지 않고 네 개의 고정된 수를 보여 줍니다.

이 페이지의 두 개수는 무엇이 다른가요?

첫째는 되풀이를 그대로 둔 채 소인수를 세고, 둘째는 약수를 셉니다. 12에서 답은 3과 6이고 둘 다 맞습니다. 12는 2 × 2 × 3이므로 소수(素數) 조각 세 개로 만들어졌고, 1, 2, 3, 4, 6, 12가 모두 12를 나누므로 약수가 여섯입니다. 작은 입력에서는 두 값이 가까워서 혼동이 자연스럽습니다. 소인수 개수를 구하는 방법은 지수를 더하는 것이고, 약수 개수를 구하는 방법은 지수마다 1을 더해 곱하는 것입니다. 그 곱셈 때문에 둘째 값이 훨씬 빠르게 달아납니다. 소수(素數)가 한 번 더 반복될 때마다 약수 개수는 배가 되지만 소인수 개수는 하나만 늘어납니다.

소인수분해는 수마다 하나뿐인가요?

그렇고, 그것은 관례가 아니라 정리입니다. 1보다 큰 자연수는 모두 소수(素數)의 곱으로 적을 수 있고, 순서를 따지지 않으면 적는 방법이 꼭 하나입니다. 360은 언제나 2³ × 3² × 5이고, 다른 소수(素數)들의 곱으로도 적히는 일이 없습니다. 이 결과를 산술의 기본 정리라고 부르고, 그것이 없으면 분해식을 인쇄하는 일은 답이 아니라 흥미거리에 그칩니다. 이 페이지가 가장 작은 소수(素數)를 먼저 인쇄하고도 그것이 정본이라고 확신할 수 있는 이유도 같습니다. 순서는 읽기 좋으라고 고른 것이고, 고정해도 잃는 것이 없습니다.

1은 어떻게 처리하나요?

분해식으로 1을 인쇄하고, 소인수 개수는 0, 약수 개수는 1로 보고합니다. 1은 소수(素數)도 합성수도 아닙니다. 통상적인 뜻의 소인수분해가 없고, 위의 정리가 1보다 큰 수에 대해서만 서술되는 이유도 그것입니다. 그런데 결과 패널을 비워 두면 계산에 실패한 것처럼 읽히므로, 페이지는 숫자를 인쇄하고 두 개수를 정직하게 보고합니다. 1을 나누는 양의 자연수는 1뿐이므로 약수 개수는 정말로 1이고 소인수 개수는 정말로 0입니다. 입력 범위가 1에서 시작하므로 거부하지 않고 받아들입니다. 자기 범위의 맨 아래 값을 거부하는 쪽이 오히려 설명할 것이 많아집니다.

왜 100만에서 멈추나요?

쓰는 방법이 시험 나눗셈이고 그 비용이 수의 제곱근에 따라 늘기 때문입니다. 100만 근처의 수에서 소수(素數)를 찾는 일은 1000까지의 약수만 시험하면 되므로 순식간입니다. 스무 자리 수에서는 100억까지 시험해야 하는데, 그건 순식간이 아닙니다. 이 벌어짐은 구현의 세부가 아니라 문제 자체의 성질이고, 큰 수를 분해하기 어렵다는 점 위에 공개키 암호가 세워져 있습니다. 100만 안에서는 모든 답이 곧바로 돌아오고, 상한은 타임아웃 속에 숨기지 않고 입력에 적어 두었습니다.

약수 목록 대신 분해식이 필요한 때는 언제인가요?

질문이 목록에 들어 있는지가 아니라 구조에 관한 것일 때입니다. 72의 제곱근을 정리하려면 72 = 2³ × 3²이 필요합니다. 지수가 각 소수(素數)를 근호 밖으로 얼마나 꺼낼 수 있는지 알려 주어 6√2가 나오기 때문입니다. 두 수의 최대공약수를 구하려면 두 분해식이 모두 필요합니다. 답이 공통인 소수(素數)를 작은 지수로 택한 것이기 때문입니다. 어떤 수가 완전제곱수인지 확인하는 일은 지수를 한 번 보는 것으로 끝납니다. 모두 짝수면 그렇습니다. 약수를 나열하는 것은 다른 질문이고, 수에 따라서는 훨씬 긴 답이 됩니다. 720720에는 약수가 240개나 되어 인쇄할 것도 많고 볼 것도 많지 않습니다. 그런 목록이 필요할 때는 이 사이트의 약수 페이지가 그것을 보여 줍니다.

소수가 한 번만 나올 때 지수를 인쇄하지 않는 이유는 무엇인가요?

5 하나에 5^1이라고 적는 것은 소음이기 때문입니다. 수학의 관례는 지수가 1보다 클 때만 지수를 인쇄하는 것이므로, 360은 2^3 * 3^2 * 5이고 마지막 항이 맨몸으로 남습니다. 빠뜨려서 잃는 것은 없습니다. 지수가 없다는 것이 곧 지수가 1이라는 뜻이고, 이는 모호하지 않습니다. 소수(素數) 하나하나가 한 번씩만 나오는 수, 곧 제곱인수가 없는 수의 분해식은 캐럿이 하나도 없는 평범한 곱으로 읽힙니다. 소수(素數)인 97이 97^1이 아니라 그냥 97로 인쇄되는 것도 같은 관례입니다.

• Prime Factorization — 어떤 자연수를 소수의 곱으로 적는 일, 그리고 그 소수들을 찾아내는 알고리즘 — Wolfram MathWorld (United States)
• Fundamental Theorem of Arithmetic — 1보다 큰 모든 자연수에 소인수분해가 꼭 하나씩 있다는 정리이고, 그것을 인쇄할 값어치로 만드는 사실 — Wolfram MathWorld (United States)
• Divisor Function — 양의 약수의 개수, 지수에서 그것을 만들어 내는 공식, 그리고 하나의 소수의 거듭제곱 위에서 그것이 어떻게 움직이는지 — Wolfram MathWorld (United States)
• 教育部关于印发义务教育课程方案和课程标准(2022年版)的通知 — 이 통지의 첨부 목록 제5항이 《义务教育数学课程标准(2022年版)》에 해당하며, 소인수분해와 약수, 배수는 이 교육과정의 수와 대수 영역 내용이므로 원문과 학년군 요구는 이 첨부를 기준으로 합니다 — 中华人民共和国教育部