소수, 합성수, 에라토스테네스의 체

 

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 를 자연수라고 해요.

 

자연수를 분류하는 방법으로는 짝수( 2, 4, 6, 8, 10,) 와 홀수(1, 3, 5, 7, 9,)가 있습니다.

 

또 무엇이 있을까요?

 

바로 소수와 합성수 그리고 1로 분류 할 수 있습니다.

 

그럼 소수와 합성수는 무엇인지 알아볼까요?

 

 

< 소수(prime number) >

 

소수는 1보다 큰 자연수 중에서 1과 그 수 자신만을 약수로 가지는 수로 정의하므로

 

소수는 약수가 두 개라는 것을 알 수 있어요.

 

예를들어 2의 약수는 1과 2 두 개이므로 2는 소수, 17의 약수는 1과 17 두 개이므로 17은 소수가 됩니다.

 

[참고: 약수, 배수]

 

약수) 어떤 수를 나누어 떨어지게 하는 수.

예) 4÷1=4 ,  4÷2=2 ,  4÷3=1.333,  4÷4=1 이므로  4를 나누어 떨어지게 하는 수 1, 2, 4는 4의 약수이다.

 

배수) 어떤 수를 1배, 2배, 3배,한 수.

예) 4×1=4,  4×2=8,  4×3=12,  이므로  4를 1배, 2배, 3배,한 수 4, 8, 12,이 4의 배수 이다.

  

< 합성수(composite number) >

 

합성수는 1보다 큰 자연수 중에서 1과 그 수 자신 이외에 또 다른수를 약수로 가지는 수로 정의합니다.

 

따라서 합성수는 약수가 세 개 이상이 됩니다.

 

예를들어 4의 약수는 1과 2 , 4이므로 4는 합성수,  20의 약수는 1과 2 , 4 , 5 , 10 , 20이므로 20은 합성수입니다.

 

1은 약수가 한 개이므로 1은 소수도 합성수도 아니라는 것을 꼭 기억해 두세요.

 

 

합성수의 약수는 세 개 이상으로 다양하지만 소수는 약수가 두 개로 정해지니까 정말 특별하죠?

그런 특별한 소수를 쉽게 찾아볼까요?

 

< 소수 쉽게 찾기 - 에라토스테네스의 체 >

 

1부터 n까지의 자연수 중에서 소수를 찾기 위해,

1부터 n까지 자연수를 나열 한 후, 1과 합성수를 지워나가는 방법입니다. 

 

예를들어 1부터 30 까지의 자연수 중에서 소수를 찾기 위해 1부터 30까지 씁니다.

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30

 

➊ 1은 소수가 아니므로 지웁니다.

 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30

 
➋ 남은 수 중 가장 작은 수인 2는 소수 이므로 , 2보다 큰 2의 배수를 모두 지웁니다.

 2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29

 

➌ 2를 제외한 남은 수 중 가장 작은 수인 3은 소수이므로, 3보다 큰 3의 배수를 모두 지웁니다.
 2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29

 

➍ 2, 3을 제외한 남은 수 중 가장 작은 수인 5는 소수이므로, 5보다 큰 5의 배수를 모두 지웁니다.

 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

 

 이처럼 남은 수 중 가장 작은 소수를 찾고, 그 수보다 큰 그 수의 배수를 모두 지우는 작업을 반복하면
2, 3, 5, 7, 11, 13, 17, 19, 23, 29 와 같은 소수만 남게 됩니다.

 

여기서 왜 7이상 소수에 대해서는 지우는 작업을 하지 않을까요?

하지 않아도 앞에서 다 지워졌기 때문입니다.

 

이므로 2, 3, 5 소수의 배수만 확인하면 됩니다.

 

예를들어 1부터 50까지의 소수를 찾을 때는 이므로 2, 3, 5, 7 소수의 배수만 확인하고,

1부터 150까지의 소수를 찾을 때는 이므로 2, 3, 5, 7, 11 소수의 배수만 확인하면 됩니다.

 

즉, 1부터 n까지의 자연수 중에서 소수를 찾으려면 제곱이 n보다 작거나 같은 소수 중에서 가장 큰 소수를 찾아 그 소수의 배수까지만 확인하면 됩니다.

( 가장 큰 소수의 배수까지만 확인하는 이유를 알기 위해서는, 에라토스테네스의 체의 근거가 되는 정리를 알고 있어야해요.

그런데 중학교 과정에서는 몰라도 됩니다. 아래 ※별해는 이와 같이 확인하는 이유에 관한 설명입니다. )

 

 

 

* 초등학교때 배웠던 소수(decimal)와 분수 에서의 소수(decimal)는 소수(prime number) 와 합성수 의 소수(prime number) 와는 전혀 다릅니다.

 예) 소수(decimal) : 0.1, 0.9, 2.34 

     소수(prime number) : 2, 3, 5

 

 

 

 

 ※ 별해) 전공수학 -  정수론

 

정리) 양의 정수 n이 합성수이면, n의 소인수 중에 인 소인수 p가 존재한다.

 

pf) 양의 정수 n이 합성수이면 정의에 의하여 n=de, 인 정수 d, e가 존재한다.

이므로 이고 따라서 이다.

이므로 d의 소인수 p가 존재하고 p|d, d|n이므로 p|n 이고 p≤d 이므로 이다.

( n이하의 합성수 m을 택하면 위 정리에 의하여 소인수p가 존재하고 이므로 이다. 따라서 보다 작거나 같은 소인수의 배수만 지우면 n이하의 합성수가 모두 지워지므로

에라토스테네스의 체에서 이하의 소수만 확인하면 된다. )

 

 

정리) 소수는 무한히 많다.

 

pf) 유한 개의 소수 만이 존재한다고 가정하자.

N =  +1 이라고 하면  이므로 N의 소인수 P가 존재한다.

가정에 의해 P는  중의 어느 하나와 같으므로  P | N,  P |  이다

따라서 p |  즉 P|1 이 되어 모순이다.