소수 판별 계산기

소수 판별 계산기

선두 AI Skill PRO

계산 입력

공식

소수여부(N)={1N>1그리고∄d∈[2,N]:Nmodd=00그 외\text{소수여부}(\text{N}) = \begin{cases} 1 & \text{N} > 1 \ \text{그리고} \ \nexists \, d \in [2, \sqrt{\text{N}}] : \text{N} \bmod d = 0 \\[0.5em] 0 & \text{그 외} \end{cases}
사용 통계

광고

결과

221, 소수일까요?
아니요
이 수는 합성수입니다
검사한 숫자 221
가장 작은 약수 (> 1) 13
소인수분해 221 = 13 × 17

이 페이지의 오류 신고

소수란 무엇일까요?

소수(素數)는 1보다 큰 정수 중에서 1과 자기 자신, 이렇게 정확히 두 개의 양의 약수만 가지는 수를 말합니다. 2, 3, 5, 7, 11, 13 등이 대표적인 예입니다. 1보다 크면서 소수가 아닌 수는 합성수라고 부르며, 더 작은 정수들의 곱으로 나타낼 수 있습니다. 이 계산기는 입력한 숫자가 소수인지 즉시 알려주고, 소수가 아니라면 그 수를 나누는 가장 작은 약수까지 보여줍니다.

소수를 한 줄의 점으로, 합성수를 직사각형 격자로 배열해 비교한 그림
소수는 직사각형을 만들 수 없지만(\(1 \times n\) 제외), 합성수는 만들 수 있습니다.

계산기 사용 방법

입력란에 0 이상의 정수를 입력한 뒤 확인을 누르세요. 결과 박스에는 해당 숫자가 소수이면 예(YES), 합성수이면 아니오(NO)가 표시됩니다. 합성수인 경우에는 1보다 큰 가장 작은 약수가 표에 나타나는데, 이는 전체 소인수분해를 시작하는 출발점으로 활용할 수 있습니다.

공식 자세히 살펴보기

소수 여부를 효율적으로 확인하려면 \(n\)의 제곱근까지의 약수만 검사하면 됩니다. 만약 \(n\)이 제곱근보다 큰 약수를 가진다면, 반드시 제곱근보다 작은 짝이 되는 약수도 함께 존재하기 때문에 그 지점까지만 확인하면 충분합니다. 수식으로 표현하면, \(n > 1\)이고 2부터 \(\lfloor\sqrt{n}\rfloor\)까지의 모든 정수 \(i\)에 대해 \(n \bmod i \neq 0\)일 때 \(n\)은 소수입니다.

$$n \text{ is prime} \iff n > 1 \text{ and } n \bmod i \neq 0 \;\; \forall\, i \in [2, \sqrt{n}]$$

이 방법은 \(n\)보다 작은 모든 수를 일일이 검사하는 것보다 계산량을 크게 줄여 줍니다.

광고
2부터 n까지 약수를 나타낸 수직선으로, n의 제곱근에 표시가 있어 아래 절반만 확인하면 됨을 보여줌
약수는 \(n\)의 제곱근까지만 확인하면 됩니다.

예제로 이해하기

\(n = 97\)을 살펴봅시다. 제곱근이 약 \(9.85\)이므로 약수 2, 3, 5, 7, 9만 검사하면 됩니다. 97은 홀수이고 3, 5, 7로도 나누어떨어지지 않으므로 어느 것도 97을 정확히 나누지 못합니다. 따라서 97은 소수입니다. 이번에는 \(n = 91\)을 봅시다. 2, 3, 5를 차례로 검사한 뒤 7을 시도하면 \(91 \div 7 = 13\)으로 딱 떨어집니다. 그러므로 91은 가장 작은 약수가 7인 합성수입니다.

광고

손으로 소수인지 확인하는 방법

소수는 1보다 큰 자연수로, 양의 약수가 1과 자기 자신뿐인 수입니다. 자연수 \(n\)이 소수인지 시험하려면 \(\lfloor\sqrt{n}\rfloor\)까지의 약수만 찾아보면 됩니다. 만약 \(n\)이 제곱근보다 큰 약수를 가진다면, 제곱근보다 작은 짝이 되는 약수도 반드시 가집니다.

  1. \(n < 2\)인 경우를 제외합니다. 0, 1과 음수는 소수가 아닙니다.
  2. 2와 3은 소수로 인정합니다. 둘 다 소수입니다. 2는 유일한 짝수 소수입니다.
  3. 짝수는 제외합니다. 2보다 큰 짝수 \(n\)은 2로 나누어떨어지므로 합성수입니다.
  4. \(\lfloor\sqrt{n}\rfloor\)을 계산합니다. 제곱이 \(n\) 이하가 되는 가장 큰 정수를 찾습니다. 예를 들어 \(14^2 = 196 \le 221 < 225 = 15^2\)이므로 \(\lfloor\sqrt{221}\rfloor = 14\)입니다.
  5. 3부터 \(\lfloor\sqrt{n}\rfloor\)까지의 홀수 약수, 또는 소수만 시험합니다. 각 후보 \(d\)에 대해 \(n \bmod d = 0\)인지 확인합니다. 아래의 나눗셈 판정법을 쓰면 더 빠릅니다.
  6. 결론을 내립니다. 약수가 하나라도 발견되면 \(n\)은 합성수이며, 처음 찾은 약수가 1보다 큰 가장 작은 약수입니다. 어떤 수로도 나누어떨어지지 않으면 \(n\)은 소수입니다.

나눗셈 판정법

  • 3으로 나누어떨어짐: 각 자릿수의 합이 3으로 나누어떨어집니다. 예: 51은 5 + 1 = 6이므로 51 = 3 × 17입니다.
  • 5로 나누어떨어짐: 일의 자리 숫자가 0 또는 5입니다.
  • 11로 나누어떨어짐: 오른쪽이나 왼쪽에서부터 자릿수의 교대합을 구합니다. 결과가 0 또는 11의 배수이면 그 수는 11로 나누어떨어집니다. 예: 121은 1 − 2 + 1 = 0이므로 121 = 11 × 11입니다.

풀이 예 1: 221은 소수인가?

  1. 221 ≥ 2이고, 홀수이며, 2도 3도 아닙니다.
  2. \(\lfloor\sqrt{221}\rfloor = 14\)이므로 소수 3, 5, 7, 11, 13을 시험합니다.
  3. 3: 자릿수의 합은 2 + 2 + 1 = 5이므로 3으로 나누어떨어지지 않습니다.
  4. 5: 일의 자리 숫자가 1이므로 아닙니다.
  5. 7: \(7 \times 31 = 217\)이고 \(221 - 217 = 4\)이므로 나머지가 있어 아닙니다.
  6. 11: 교대합은 1 − 2 + 2 = 1이므로 아닙니다.
  7. 13: \(13 \times 17 = 221\)이므로 13은 221의 약수입니다.

221은 합성수이며, 가장 작은 약수는 13입니다.

풀이 예 2: 97은 소수인가?

  1. 97은 홀수이고 3보다 큽니다.
  2. \(9^2 = 81 \le 97 < 100 = 10^2\)이므로 \(\lfloor\sqrt{97}\rfloor = 9\)입니다. 3, 5, 7을 시험합니다.
  3. 3: 자릿수의 합은 9 + 7 = 16이므로 3으로 나누어떨어지지 않습니다.
  4. 5: 일의 자리 숫자가 7이므로 아닙니다.
  5. 7: \(7 \times 13 = 91\)이고 \(97 - 91 = 6\)이므로 나머지가 있어 아닙니다.

9 이하의 어떤 수도 97을 나누지 못하므로 97은 소수입니다.

이 손 계산법은 작은 수와 중간 크기의 수에 잘 맞습니다. 매우 큰 수에서는 시험 나눗셈이 느려지므로, 대신 전문적인 소수 판정법이 사용됩니다.

계산 규칙과 경계 사례

아래 사례는 모두 이 계산기로 실제 계산한 것이며, 결과 열은 계산기가 실제로 돌려준 값입니다.

사례입력결과
1은 소수인가1아니요
2는 소수인가2예
0은 소수인가0아니요

2026-11-08 확인

자주 묻는 질문

1은 소수인가요? 아닙니다. 정의상 소수는 1보다 커야 하므로, 1은 소수도 합성수도 아닙니다.

2는 소수인가요? 네. 2는 유일한 짝수 소수입니다. 2를 제외한 모든 짝수는 2로 나누어떨어지기 때문입니다.

왜 제곱근까지만 검사하나요? 약수는 곱해서 \(n\)이 되는 짝으로 존재합니다. 만약 두 약수가 모두 \(\sqrt{n}\)보다 크다면 그 곱이 \(n\)을 넘어서게 되어 모순이 됩니다. 따라서 모든 약수 짝에서 적어도 하나는 반드시 \(\sqrt{n}\) 이하입니다.

최종 업데이트:

수학 및 통계 인기 계산기

수학 및 통계 계산기 전체 보기