소수 판별법: 제곱근까지만 확인하면 되는 이유

어떤 수가 소수인지 판별하는 데는 정해진 계산 순서가 있습니다. 1은 정의상 처음부터 제외되고, 2와 3을 먼저 확인한 다음, 남은 후보는 제곱근까지만 나눠보면 결론이 납니다.

소수 판별 로직을 이해하려는 사람이나 특정 숫자를 손으로 검산해보려는 사람이 막히는 지점은 대부분 이 순서 안에 있습니다.

요약 ① 소수는 "1과 자기 자신만을 약수로 갖는 1보다 큰 자연수"라서 1은 정의상 제외됩니다. ② 2와 3을 먼저 걸러내면 남는 후보는 6으로 나눈 나머지가 1 또는 5인 수로 줄어듭니다. ③ n=a×b일 때 a와 b 중 하나는 반드시 제곱근 이하이므로, 제곱근까지만 나눠보면 충분합니다.

소수인지 판별하다가 막히는 순간

두 자릿수, 세 자릿수 정도의 수를 손으로 확인하다 보면 어디까지 나눠봐야 멈출 수 있는지 애매해지는 순간이 옵니다.

예를 들어 91이 소수인지 확인한다면, 2로도 3으로도 나누어떨어지지 않으니 계속 5, 7, 11, 13… 하고 나눠봐야 할 것 같은데 언제 멈춰야 할지 기준이 없으면 끝없이 나눠보게 됩니다.

코딩 문제를 풀 때도 같은 지점에서 막힙니다. "n이 소수인지 확인하는 함수를 작성하라"는 문제에서 "제곱근까지만 나눠보면 된다"는 힌트는 자주 나오지만, 왜 그래도 되는지 근거를 모르면 코드를 외워서 쓰는 것과 다르지 않습니다.

정답만 알고 계산 원리를 모르면 숫자가 조금만 커져도(다섯 자리, 여섯 자리) 검산이 맞는지조차 스스로 확인할 수 없습니다. 판별 순서를 한 번 제대로 정리해두면 이 문제가 풀립니다.

소수를 손으로 판별하는 계산 순서

아래 순서는 판별기가 내부적으로 계산하는 순서와 같습니다. 이 순서대로 따라가면 어떤 자연수든 손으로도 소수 여부를 확인할 수 있습니다.

1~2단계 — 1은 제외하고, 2·3부터 확인한다

소수의 정의는 "1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수"입니다. 1은 약수가 자기 자신(1) 하나뿐이라 이 정의에 들어맞지 않아 처음부터 대상에서 빠집니다. 2와 3은 그 자체로 가장 작은 소수이므로 바로 소수로 판정됩니다.

3~4단계 — 2·3의 배수를 걸러내고 후보를 좁힌다

남은 수가 2의 배수(짝수)이거나 3의 배수라면 그 자리에서 소수가 아니라는 결론이 나고, 나누어떨어진 값(2 또는 3)이 약수로 표시됩니다. 예를 들어 51은 3으로 나누어떨어지므로 이 단계에서 바로 합성수로 판정됩니다.

2와 3의 배수를 모두 제외하고 나면, 남는 수는 6으로 나눈 나머지가 1이거나 5인 수뿐입니다(6k+1, 6k+5 꼴).

그래서 5부터 시작해 5, 7, 11, 13, 17, 19처럼 6씩 뛰면서 두 후보(i, i+2)만 나눠보면 나머지 경우는 검사할 필요가 없습니다.

5단계 — 제곱근까지만 나눠보고 멈춘다

n = a × b로 나누어떨어진다면 a와 b 중 적어도 하나는 반드시 √n 이하입니다. 두 값이 모두 √n보다 크면 곱이 n을 넘어서기 때문입니다. 그러므로 √n까지 나누어떨어지는 값이 없다면 그 수는 소수로 확정됩니다.

91과 97로 직접 확인해보기

91은 2의 배수도 3의 배수도 아니므로 3단계를 통과합니다. √91은 약 9.54이므로 나눠볼 후보는 5와 7뿐입니다.

91을 5로 나누면 나누어떨어지지 않지만 7로 나누면 91 = 7 × 13으로 나누어떨어지므로, 91은 합성수이고 약수는 7이라는 결론이 나옵니다.

97은 어떨까요. 마찬가지로 2, 3의 배수가 아니고 √97은 약 9.85이므로 후보는 역시 5와 7입니다. 두 값 모두 97을 나누어떨어뜨리지 못하므로 그 이상 확인할 필요 없이 97은 소수로 확정됩니다.

손으로 이 순서를 따라가 본 뒤, 같은 계산을 도구가 어떻게 즉시 처리하는지 비교해보면 이해가 빨라집니다. 저희 도구로 확인하기.

직접 해보기 →

판별 결과를 읽을 때 흔히 헷갈리는 부분

소수 판별 결과 자체는 명확하지만, 화면에 표시되는 문구를 해석할 때 오해가 생기는 지점이 두 곳 있습니다.

"약수"로 표시되는 값은 그 수의 모든 약수가 아니라, 판별 과정에서 가장 먼저 나누어떨어진 값 — 즉 가장 작은 소인수입니다. 91의 실제 약수는 1, 7, 13, 91 네 개지만 화면에는 계산 중 가장 먼저 발견된 7만 표시됩니다.

숫자가 커질수록 √n까지 나눠봐야 하는 후보 개수도 함께 늘어납니다. 100만에 가까운 일곱 자리 수는 √n이 1000 근처라, 6칸 간격 최적화를 적용해도 수백 개의 후보를 나눠봐야 판별이 끝납니다. 이 지점부터는 손으로 검산하는 것이 사실상 비현실적입니다.

정리

• 소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 갖는 수입니다. 약수가 하나뿐인 1은 정의상 제외됩니다.
• 2와 3을 먼저 확인하고 그 배수를 걸러내면, 남은 후보는 6으로 나눈 나머지가 1 또는 5인 수로 줄어듭니다.
• n = a × b일 때 a, b 중 하나는 반드시 √n 이하이므로, √n까지만 나눠보면 소수 여부를 확정할 수 있습니다.
• 화면에 표시되는 "약수"는 그 수의 모든 약수가 아니라 계산 중 가장 먼저 발견된 가장 작은 소인수입니다.
• 자릿수가 커질수록 나눠봐야 할 후보 수도 늘어나므로, 손으로 검산하기보다 판별기로 즉시 확인하는 편이 정확합니다.

자주 묻는 질문

1은 왜 소수가 아닌가요?

소수의 정의는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수입니다. 1은 약수가 자기 자신(1) 하나뿐이라 이 조건에 들어맞지 않습니다. 그래서 1은 소수도 합성수도 아닌 별도의 수로 다룹니다.

판별 결과에 나오는 "약수"는 그 수의 모든 약수인가요?

아닙니다. 계산 과정에서 처음 나누어떨어진 값 하나만 표시되며, 이는 항상 그 수의 가장 작은 소인수입니다. 91은 실제로 1, 7, 13, 91 네 개의 약수를 갖지만 화면에는 7만 나타납니다.

왜 짝수 중에는 2만 소수인가요?

2보다 큰 짝수는 모두 2로 나누어떨어지므로 약수가 1, 2, 자기 자신으로 세 개 이상이 되어 소수 조건을 만족하지 못합니다. 2는 짝수이면서 동시에 약수가 1과 2 두 개뿐인 유일한 경우라 소수로 남습니다.

소수 목록은 어떤 방식으로 만들어지나요?

에라토스테네스의 체 방식을 사용합니다. 2부터 지정한 범위까지 나열해 놓고 소수의 배수를 순서대로 지워나가면서 끝까지 남는 수만 소수로 남기는 방식입니다.

입력 가능한 범위는 최대 100만이며, 이를 넘는 값을 입력하면 자동으로 100만까지로 제한됩니다.