에라스토 테네스 체 [Sieve of Eratosthenes] 및 증명 이해하기

오늘은 특정 자연수 이하의 소수를 찾는 알고리즘인

에라스토테네스의 체, 그리고 여기에 활용되는 소수 관련 수학적 정의를 증명하는 시간을 가져 보겠습니다.

 

 

에라스토테네스의 체 [Sieve of Eratosthenes]

에라스토테네스의 체란 기계의 도움 없이 순수 손 계산을 사용하여

특정 자연수 이하의 소수를 구하는 유일한 알고리즘입니다.

 

에라스토테네스의 체를 설명하기 전에 다음 수학적 정의를 설명하겠습니다.

n이 합성수라면 

p | n, p <= √n을 만족하는 소수 p가 반드시 존재한다.

 

증명을 통해서 위 정리가 맞는 내용인지 확인해 봅시다.

 

 

만약 n이 합성수라면

n을 다음과 같이 나타낼 수 있습니다.

 

1 < a <= b < n 만족하는 적당한 자연수 a와 b에 대하여

n = ab >= a^2

 

따라서 a <=  √n 입니다.

그러므로, n이 합성수라면 √n보다 작으며 n을 나누어 떨어트리는 자연수 a가 존재한다는 것이 증명되었습니다.

 

 

여기서 Case를 나눠보도록 합시다

 

Case 1 : 자연수 a가 소수(Prime Number)인 경우

자연수 a가 소수라면

 

"n이 합성수라면 

p | n, p <= √n을 만족하는 소수 p가 반드시 존재한다"

라는 위 정의에 부합하므로, 위 명제가 참이 됩니다.

 

 

Case 2 : 자연수 a가 합성수인 경우

 

자연수 a가 합성수라면

1보다 크고 a보다 작은 자연수 중

a를 나누어 떨어트리는 소수 p가 존재합니다.

 

이 소수 p에 대하여

p | a 이고 a | n 이므로,

p | n입니다.

 

 

1 < p < a <= √n < n 이므로

n이 합성수라면 

p | n, p <= √n을 만족하는 소수 p가 반드시 존재한다.

라는 위 명제가 참이 됩니다.

 

 

따라서 모든 경우에 있어 위 정의가 참이 된다는 것을 증명하였습니다.

 

 

 

n이 합성수이면 √n보다 작거나 같은 수들 중 n을 나누어 떨어 트리는 소수 p가 반드시 존재한다는 것.

바꿔 말하면,

 

 

n이 만약 소수라면 √n보다 작거나 같은 수들 중 n을 나누어 떨어 트리는 소수 p가 존재하지 않습니다.

특정 수가 소수인지 아닌지를 판별할 때 엄청난 수고를 덜어주는 정리입니다.

 

 

예를들어 111이 소수인지 아닌지를 판별해 보도록 합시다

이 정리를 알기 전에는 111이하의 모든 소수를 하나하나 구해서,

이 소수들로 111이 나누어 떨어지는지를 보아야 했습니다.

 

하지만 위 정리를 적용 해보면,

10 < √111 < 11이기에

11이하의 소수들인 2,3,5,7,11으로 나누어 떨어지지만 않는다면 111은 소수라는 사실이 증명됩니다.

 

이 사실을 한번 적용해 보도록 하겠습니다.

 

예를 들어,

50이하의 자연수 중 합성수들을 모두 제외시키고,

소수만을 골라내 보도록 합시다.

 

그러면 50이하의 수들 중 합성수가 뭔지를 판별해내고

그것들을 제외시켜야 합니다.

 

50 이하의 합성수들에는 다음과 같은 특징이 있습니다.

50이하의 임의의 합성수를 골라 a라고 하면

 

1 < a <=50입니다.

a가 합성수이기 때문에

√a이하의 수들 중 a를 나누어 떨어트리는 소수 p가 존재하고

1 < p < √a입니다.

 

 

여기서 √a <= √50 이기 때문에

합성수 a를 떨어트리는 소수 p에 대하여

p <= √a <= √50을 만족합니다.

 

 

50이하의 합성수들은 모두 √50보다 작은 소수들에 의하여 나누어지기 때문에

√50 이하의 소수들을 구하여,

그 소수들의 배수들을 하나 하나 소거해 나가면

결국 50 이하의 모든 합성수들이 제거되는 것입니다. 

 

 

7 < √50 < 8이므로

8 이하의 소수인 2,3,5,7의 배수들을 소거해 나가면 50 이하의 합성수들이 모두 제거됩니다. 

 

그 결과 소수 1,11,13,17,19,23,29,31,37,41,43,47들이 남게 되었습니다.

 

이상 에라스토테네스의 체와, 소수와 관련된 수학적 정의를 증명해보았습니다.

감사합니다.