소수 판별 계산기

소수 판별 계산기

인기 AI Skill PRO

계산 입력

1보다 큰 정수를 입력하세요.

공식

n=수 는 소수⇔n>1∧∄d∈[2,⌊n⌋]:nmodd=0n = \text{수} \text{ 는 소수} \iff n > 1 \;\wedge\; \nexists\, d \in [\,2,\ \lfloor\sqrt{n}\rfloor\,] : n \bmod d = 0
사용 통계

광고

결과

결과: 2
소수
소수 판별 결과
수 2
약수 약수는 1과 2
이전 소수 이전 소수가 없습니다
다음 소수 3

이 페이지의 오류 신고

소수란 무엇인가요?

소수는 1보다 큰 자연수 중에서 양의 약수가 1과 자기 자신, 이렇게 딱 두 개만 있는 수입니다. 반대로 약수가 세 개 이상인 수는 합성수라고 부릅니다. 숫자 1은 좀 특별한데, 약수가 1 하나뿐이라서 소수도 합성수도 아닙니다. 이 계산기는 입력한 수가 소수인지 합성수인지 판별하고, 약수를 모두 나열하며, 바로 앞과 뒤에 오는 소수까지 함께 보여 줍니다.

소수를 점 한 줄로 배열한 경우와 합성수를 점의 직사각형 격자로 배열한 경우의 비교
소수는 점으로 직사각형을 만들 수 없지만 합성수는 만들 수 있다.

사용 방법

1보다 큰 정수를 입력하고 실행 버튼을 누르기만 하면 됩니다. 입력한 수가 소수인지 합성수인지 분류해 주고, 그 수를 다시 한번 표시한 뒤, (합성수라면) 모든 약수를 보여 줍니다. 또한 그 수보다 작은 가장 큰 소수와 그 수보다 큰 가장 작은 소수도 알려 줍니다.

계산 원리

이 계산기는 6k±1 최적화를 적용한 결정적 시산법(trial division)을 사용합니다. 먼저 2와 3은 이미 알려진 소수이므로 따로 처리하고, 짝수와 3의 배수는 곧바로 걸러냅니다. 그다음에는 6k-1, 6k+1 형태의 후보 약수(5, 7, 11, 13, ...)만 n의 제곱근까지 나눠 봅니다. 이 중 어느 것으로도 n이 나누어떨어지지 않으면 n은 소수입니다. 제곱근까지만 확인하면 되는 이유는, 제곱근보다 큰 약수는 반드시 제곱근보다 작은 약수와 짝을 이루기 때문입니다.

$$n = \text{Number} \text{ is prime} \iff n > 1 \;\wedge\; \nexists\, d \in [\,2,\ \lfloor\sqrt{n}\rfloor\,] : n \bmod d = 0$$

광고
시험 나눗셈이 n의 제곱근까지의 약수만 확인하는 것을 보여주는 다이어그램
시험 나눗셈은 2부터 n의 제곱근까지의 약수만 확인하면 된다.

예제로 살펴보기

\(n = 97\)을 예로 들어 보겠습니다. 97의 제곱근은 약 9.85입니다. 97은 홀수이고 3의 배수도 아닙니다. 그래서 5로 나눠 보면(\(97 \bmod 5 = 2\)), 7로 나눠 봅니다(\(97 \bmod 7 = 6\)). 다음 후보는 11인데, \(11 \times 11 = 121 > 97\)이므로 여기서 멈춥니다. 어떤 약수도 찾지 못했으니 97은 소수입니다. 바로 앞 소수는 89, 바로 뒤 소수는 101입니다.

소수와 합성수: 예시 입력값 비교

표는 시행 나눗셈 검사법이 일곱 개의 입력값을 어떻게 처리하는지 보여 줍니다. 제곱근 상한은 \(\lfloor\sqrt{n}\rfloor\)이며, 이는 반드시 시험해야 하는 가장 큰 약수입니다. 2부터 이 상한까지의 어떤 정수도 \(n\)을 나누지 못하면 \(n\)은 소수입니다. 이전 소수와 다음 소수는 \(n\)보다 각각 작고 큰 가장 가까운 소수입니다.

입력값 n 상태 모든 인수 이전 소수 다음 소수 제곱근 상한 \(\lfloor\sqrt{n}\rfloor\)
2 소수 1, 2 없음 3 1 (시험할 약수 없음; 2는 유일한 짝수 소수)
9 합성수 1, 3, 9 7 11 3 (3이 9를 나눔)
15 합성수 1, 3, 5, 15 13 17 3 (3이 15를 나눔)
49 합성수 1, 7, 49 47 53 7 (7이 49를 나눔)
91 합성수 1, 7, 13, 91 89 97 9 (7이 91을 나눔)
97 소수 1, 97 89 101 9 (2, 3, 5, 7, 9 모두 97을 나누지 못함)
121 합성수 1, 11, 121 113 127 11 (11이 121을 나눔)

소수처럼 보이는 합성수: 49, 91, 121은 홀수이고 3이나 5로 나누어떨어지지 않아서 소수로 착각하기 쉽습니다.

  • \(49 = 7 \times 7\)
  • \(91 = 7 \times 13\)
  • \(121 = 11 \times 11\)

이 수들은 각각 제곱근 상한 이하에 약수를 가지고 있으므로, 2, 3, 5만 검사하면 잘못 소수라고 판단하게 됩니다. 반면 97은 9까지 약수가 없으므로 소수입니다.

광고

핵심 용어와 정의

소수
1보다 큰 정수로서 양의 약수가 1과 자기 자신뿐인 수 (예: 2, 3, 5, 7, 97).
합성수
1보다 큰 정수로서 1과 자기 자신이 아닌 약수를 적어도 하나 가지는 수 (예: 9, 49, 91). 0과 1은 소수도 합성수도 아닙니다.
인수 / 약수
나머지 없이 \(n\)을 나누는 정수 \(d\). 15의 인수는 1, 3, 5, 15입니다.
나머지 연산(mod)
나눗셈 후의 나머지입니다. \(n \bmod d = 0\)은 \(d\)가 \(n\)을 정확히 나눈다는 뜻입니다. 예를 들어 \(91 \bmod 7 = 0\)이지만 \(97 \bmod 7 = 6\)입니다.
제곱근 상한
\(n = a \times b\)이고 \(a \le b\)이면 \(a \le \sqrt{n}\)입니다. 따라서 모든 합성수는 2부터 \(\lfloor\sqrt{n}\rfloor\) 사이에 약수를 가지며, 그 이상까지 시험할 필요는 없습니다.
시행 나눗셈
\(n\)을 2부터 \(\lfloor\sqrt{n}\rfloor\)까지의 후보 약수로 나누는 소수 판별법입니다. 어떤 나눗셈에서든 나머지가 0이면 \(n\)은 합성수이고, 그렇지 않으면 소수입니다. 단순하고 신뢰할 수 있으며, 중간 크기의 수에서는 빠릅니다.
6k±1 형태
3보다 큰 모든 소수는 어떤 정수 \(k\)에 대해 \(6k-1\) 또는 \(6k+1\)로 쓸 수 있습니다. 6을 법으로 한 다른 나머지는 2 또는 3으로 나누어떨어지기 때문입니다. 이를 이용하면 검사 후보 약수의 약 3분의 2를 건너뛸 수 있습니다. 역은 성립하지 않습니다: 25, 35, 49, 91은 이 형태이지만 합성수입니다.
쌍둥이 소수
차이가 2인 두 소수로, 예를 들어 (3, 5), (11, 13), (17, 19), (41, 43)이 있습니다. 쌍둥이 소수 쌍이 무한히 많은지는 수학에서 아직 풀리지 않은 문제입니다.

계산 규칙과 경계 사례

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

사례입력결과
1은 소수인가1소수도 합성수도 아님
2는 소수인가2소수
0은 소수인가0유효하지 않음

2026-11-08 확인

자주 묻는 질문

1은 소수인가요? 아닙니다. 1은 약수가 하나뿐이라서 소수도 합성수도 아닙니다.

2는 소수인가요? 네, 맞습니다. 2는 가장 작은 소수이자 유일한 짝수 소수입니다. 2 앞에는 소수가 없습니다.

약수는 왜 합성수일 때만 나열하나요? 소수는 정의상 약수가 1과 자기 자신뿐이라서 그 사실만 알려 주면 충분합니다. 반면 합성수는 약수가 여러 개일 수 있어, 작은 순서대로 모두 나열합니다.

최종 업데이트:

수학 및 통계 인기 계산기

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