소수와 합성수 에라토스테네스의 체 소수 판정법

작성일자 글쓴이

이번 시간에는 소수와 합성수에 대해 정리하고 소수를 찾는 방법으로 에라토스테네스의 체에 대하여 학습하고 마지막으로 소수 판정법에 대해 학습하기로 하자.

먼저 두 가지 초등학교와 중학교에서 배우는 두 소수의 의미에 대해 간단히 정리하자.

  • 小數 : 작은수라는 의미로 [소:수] 로 읽는다.
  • 素數 : 자연수의 바탕이 되는 수로 [소쑤]로 읽는다.

초등학교 때 배운 소수는 소~수로 읽고 오늘 학습할 소수는 소쑤로 발음한다는 것을 기억하고 학습을 이어가자.

자연수의 ‘분해’

수학에서 분해는 주어진 수나 식을 곱셈으로 정리하는 것을 의미한다.

$12=2 \times \color{blue}{6}= 2 \times \color{blue}{2\times3} $

자연수 $12$를 이해하려면 곱셈을 이용해 분해하는 것이 가장 좋은 방법이다. 위의 식에서 $2,3$은 자신보다 작은 두 수의 곱으로 분해 할 수 없는 수 이고, 따라서$12$는 $2\times2\times3$으로 분해된다고 할 수있다.

$2,3$과 같은 수가 더 이상 분해 할 수 없는 이유는 약수가 $1$과 ‘자신’뿐이기 때문이다. 이렇게 약수가 2개 뿐인 수를 소수 라고 하고 다음과 같이 정의 한다.

소수와 합성수 정의

소수와 합성수는 두 가지 방법으로 정의 할 수 있고 둘은 정확히 동일한 의미를 갖는다. 먼저 약수의 개수에 따른 정의 부터 살펴보자.

소수와 합성수 정의1(약수의 개수)

자연수는 약수의 개수가 $1$개, $2$개, $3$개, $4$개 $\cdots$ 인 자연수들로 구성된다. 따라서 약수의 개수에 따라 다음과 같이 정의 할 수 있다.

$\text{자연수} = \begin{cases}
\text{약수의 개수 :}\; 1 \text{ 개} \rightarrow 1\\[1em]
\text{약수의 개수 :}\; 2 \text{ 개} \rightarrow \text{소수}\\[1em]
\text{약수의 개수 :}\; 3 \text{ 개 이상} \rightarrow \text{합성수}
\end{cases}$

약수의 개수가 $3$개 이상인 수에 대해 생각해 보자. 예를 들어 $4$의 경우 ${1,2,4}$를 약수로 갖는다 즉 $1$과 ‘자신’ 이외의 약수$2$가 있어 $4=2\times2$이다. 약수의 개수가 3개 이상이면 1이 아닌 두 수의 곱으로 표현되고 이러한 성질에 따라 ‘합성수’라고 부른다.

소수와 합성수의 정의2

  • 소수 : $1$ 보다 큰 자연수 중에 1과 자신만을 약수로 가지는 수
  • 합성수 : $1$ 보다 큰 자연수 중에 1과 자신 이외의 수를 약수로 갖는 수

소수와 합성수의 성질

이제 정의를 토대로 알 수 있는 소수와 합성수에 대한 성질을 정리 보기로 하자.

  1. $1$은 소수도 합성수도 아니다.
  2. $2$를 제외한 소수는 모두 홀수이다.

첫 번째는 너무 당연하기 때문에 따로 다루지 않고 두 번째 성질에 대해 생각해 보자.

초보적인 논리 (귀류법의 기초)

$2$를 제외한 소수는 모두 홀수라는 것을 보이기 위해 무한한 소수를 다 찾아 확인한다면 죽을때 까지 이것을 증명하지 못한다. (왜냐면 소수는 무한히 많으니까..)

그렇다면 소수를 전부 찾지 않고 $2$를 제외한 소수가 모두 홀수 임을 논리적으로 보일 수 있는 방법에 대해 살펴보자.

정당화

2를 제외한 소수는 자연수 이고 자연수는 짝수와 홀수로 구분된다.

$\begin{pmatrix}{\color{#0000ff}2\text{를 제외한 소수}}\\ \text{자연수}\end{pmatrix}
\rightarrow \begin{cases} \bbox[#ffff00]{\text{짝수}}\\ \bbox[#94feff]{\text{홀수}}\end{cases}$

위와 같은 이유로 두 주장은 정확히 같은 주장이다.

  • ${\color{#0000ff}2\text{를 제외한 소수}}$는 모두 $\bbox[#94feff]{\text{홀수}}$이다.
  • ${\color{#0000ff}2\text{를 제외한 소수}}$가 $\bbox[#ffff00]{\text{짝수}}$이면 말도 안된다.

${\color{#0000ff}2\text{를 제외한 소수}}$는 ‘자연수’이므로 $\bbox[#ffff00]{\text{짝수}}$ 또는 $\bbox[#94feff]{\text{홀수}}$ 이다. 즉 ${\color{#0000ff}2\text{를 제외한 소수}}$가$\bbox[#ffff00]{\text{짝수}}$라는 것이 말도 안된다면 $\bbox[#94feff]{\text{홀수}}$라고 할 수 있다.

이제 두 번째 주장을 보이면 충분하다.

${\color{#0000ff}2\text{를 제외한 }\bbox[#ffc5fd]{\text{소수}}}$ 중에 $\bbox[#ffff00]{\text{짝수}}$가 있다고 하면 약수로 ‘$\bbox[#ffc5fd]{1}$’, ‘$\bbox[#ffc5fd]{\text{자신}}$’ 그리고 ‘$\bbox[#ffff00]{2}$’를 약수로 갖는다. 이는 $\color{#0000ff}{\bbox[#ffc5fd]{\text{소수}}}$가 약수를 $3$개 이상 갖게 되는 말도 안되는 상황이다.

따라서 ${\color{#0000ff}2\text{를 제외한 소수}}$는 모두 $\bbox[#94feff]{\text{홀수}}$이다.

이제 소수를 체계적으로 찾는 방법인 에라토스테네스의 체에 대해 정리해 보기로 하자.

에라토스테네스의 체

에라토스테네스의 체는 소수의 약수가 자신을 제외하면 1 뿐임을 이용해 소수가 아닌 수를 제외하여 소수를 찾는 방법으로 다음과 같은 과정을 거친다.

  • 소수가 아닌 $1$을 제거하고 다음을 반복한다.
  • 남아있는 가장 작은 수($\square$)에 대하여
    $\square$를 제외한 $\square$의 배수를 제거

이를 자연수에 적용하면 다음과 같다.

  • 소수가 아닌 $1$을 지운다.
  • $2$를 제외한 $\color{blue}{2 \text{의 배수}}$ : $\color{blue}{\bbox[#ffff00]{4},6,8,10,\cdots}$ 제거
  • $3$을 제외한 $\color{red}{3 \text{의 배수}}$ : $\color{red}{6,\bbox[#ffff00]{9},12,15,\cdots}$ 제거
  • $5$를 제외한 $\color{orange}{5 \text{의 배수}}$ : $\color{orange}{10,15,20,\bbox[#ffff00]{25},\cdots}$ 제거
  • $7$을 제외한 $\color{purple}{7 \text{의 배수}}$ : $\color{purple}{14,21,28,35,42,\bbox[#ffff00]{49}\cdots}$ 제거

위의 과정을 적용해 $1~50$ 까지 소수를 찾을 수 있다.

${\color{green}1},2,3,{\color{blue}4},5,{\color{blue}6},7,{\color{blue}8},{\color{red}9},{\color{blue}10}$
$11,{\color{blue}12},13,{\color{blue}14},{\color{red}15},{\color{blue}16},17,{\color{blue}18},19,{\color{blue}20}$
${\color{red}21},{\color{blue}22},23,{\color{blue}24},{\color{orange}25},{\color{blue}26},{\color{red}27},{\color{blue}28},29,{\color{blue}30}$
$31,{\color{blue}32},{\color{red}33},{\color{blue}34},{\color{orange}35},{\color{blue}36},37,{\color{blue}38},{\color{red}39},{\color{blue}40}$
$41,{\color{blue}42},43,{\color{blue}44},{\color{red}45},{\color{blue}46},47,{\color{blue}48},{\color{purple}49},{\color{blue}50}$

알고리즘을 조금더 자세히 살펴보면 다음과 같은 규칙을 찾을 수 있다.

  • $\color{blue}{2 \text{의 배수}}$로 처음 삭제되는 수 : $4$
  • $\color{red}{3 \text{의 배수}}$로 처음 삭제되는 수 : $9$
  • $\color{orange}{5 \text{의 배수}}$로 처음 삭제되는 수 : $25$
  • $\color{purple}{7 \text{의 배수}}$로 처음 삭제되는 수 : $49$

소수 판정법

어떤 자연수가 소수임을 판단할 수 있는 방법에 대해 정리하고 학습을 마무리 하도록 하자. $101$이 소수인지 판정하는 것을 예로 설명해 보기로 하자.

$101$이 소수인지 확인하는 것은 $1$을 포함하지 않는 두 수의 곱으로 표현할 수 있는지 확인하면 충분하다.

  • $100(10\times10) < \color{blue}{101} < 121(11\times11)$이므로
  • $101=\triangle \times \square$ 일 때 $\triangle, \square$둘 중 하나는 $11$보다 작다.
  • $101$이 $2,3,4,5,6,7,8,9,10$의 배수인지 아닌지 판단.
    약수가 있다면 $101$은 소수 $\times$
    약수가 없다면 $101$은 소수 $\bigcirc$

마지막 과정은 다음과 같이 더 축소 할 수 다.

  • $101$에 대하여
    $2$의 배수 $\times\rightarrow4,6,8,\cdots$의 배수도 $\times$
    $3$의 배수 $\times\rightarrow6,9,12,\cdots$의 배수도 $\times$
    $5$의 배수 $\times\rightarrow10,15,20,\cdots$의 배수도 $\times$
    $7$의 배수 $\times\rightarrow14,21,28,\cdots$의 배수도 $\times$
    $\cdots$

이러한 사고는 에라토스테네스의 체와 동일한 알고리즘과 동일하다. 따라서 $2,3,4,5,6,7,8,9,10$에서 배수인지 확인해야 하는 수는 ‘체’로 걸러진 ‘소수’ $2,3,5,7$이다.

$101$의 소수 판정법은 다음과 같이 요약할 수 있다.

  • $\color{blue}{10^2=100}\;\color{black}{< 101<}\;\color{blue}{11^2=121}$이므로
  • $ \color{red}{11 \text{이하의 소수 :}2,3,5,7}$에 대하여
  • 어떤 하나의 수로 나누어지면$\rightarrow$합성수,
    어떤 수로도 나누어 지지 않으면$\rightarrow$소수

소수 판정법 정리(중3)

어떤 자연수 $N$이 다음을 만족하면 소수이다.

  • $p(\text{소수})<\sqrt{N}$ 에 대해 $p$는 $N$의 약수가 아니다.

이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다.