사고력수학 - 소수판별에 대해 알아 봅니다.

길동이는 길순이에게 "너 소수가 무엇인지 알고있어?" 라고 물어 보았습니다.

길순이는 길동이에게 "그것도 몰라? 약수의 갯수가 1과 자기자신만 있는것을 소수라고 말하는 거잖아."

" 2,3,5,7... 이런 수를 말하는 거잖아.."

 

"그러면 어떤 수가 소수인지 아닌지 쉽게 판별하는 방법에 대해 알고 있어? 가령 1037이 소수인지 아닌지 빨리 알아내는 방법 같은 것 말이야"

 

"그런 방법이 있어?" 라고 길순이 길동에게 되물었습니다.

 

길동이는 다음과 같이 대답했어요.

" 어떤 수는 자기 자신과 1외에는 약수가 없는 것을 이용해서 1037이 어떤 소수로 나누어 지는지를 판별하면 돼..."

" 가령 2,3,5,7,13... 과 같은 수로 나누어 보는 것이지"

그러자 길순이가 물었어요.

" 왜 모든수에 대해서 나누어 보지 않는 거야? "

길동이 대답했습니다.

" 잘 생각해 봐... 4,6,8 같은 수는 이미 2로 나누어 지는 것이기 때문에 4의 배수가 된다면 이미 2의 배수가 되는것이지?"

"응"

" 그렇다면 소수가 아닌 수는 이미 자기 보다 작은 소수로 나누어진다는 얘기 이기 때문에 자기로 나누어 진다면 이미 그 이전의 소수로 나누어진다는 말이거든. 따라서 소수가 아닌 수로 나누어 볼 필요가 없는 거야."

"아 그렇구나"

 

이렇게 소수로 나누어 보는 것을 에라토스테네스의 체 라고도 이야기 해...

원리는 다음 그림과 같이 되는 것이지.

 

먼저 위의 그림과 같이 모든 수가 소수라고 생각하고 o으로 마킹을 해 놓는 거야.

그리고 처음 소수 2를 만나면 2씩 증가하면서 2의 배수들을 x로 마킹해 놓으면 2를 제외한 2의 배수들은 모두 소수가 아닌것이 되는 것이지.

그 다음 3에서 소수를 만나면 3의 배수들을 또 x로 마킹하는 것이지.

이런 형식으로 x로 마킹을 하는 것을 체를 친다고 하고 마지막에는 소수만 o으로 남게 되는 이치야.

 

만약 네가 1037이 소수인지 아닌지 판단을 하기 위해서는 2 부터 1037까지의 소수로 나누어 보면 소수인지 아닌지 판별을 할 수 있게 되는 것이지.

 

그러자 길순이가 다시 물어 보았습니다.

" 그런데 굳이 2부터 1037까지의 소수로 나누어 보아야 해?"

" 가령 100의 약수를 구해 보기 위해서는 1부터 10까지만 나누어 보면 100의 약수를 모두 구해 볼수 있잖아"

" 10보다 큰 약수는 10보다 작은 약수에서 이미 같은 쌍을 찾은것처럼, 즉 25 가 약수인 것을 꼭 25 x 4 는 100 이 되는 것이 아니라 이미 4에서 4 x 25 = 100 이 되는 과정을 알 수 있는 것과 같이 말야."

 

길동이가 대단하다는 듯이 길순이를 쳐다보며 말했어요.

" 정말 대단한데. 1037이 소수인지 판별하기 위해서 2부터 1037까지의 수를 모두 확인해 볼 필요는 없어, 1037의 제곱근 까지의 수까지의 소수로만 나누어 보면 되는 것이지. 100의 약수를 구하기 위해서 10까지만 계산해 보면 되는 것처럼 말이지"

 

"그러면 37보다 작은 소수까지만 나누어 보면 되겠는데? 37 x 37 = 1369 이니까, 2,3,5,7,11,13,17,19,23,29,31 으로만 나누어 보면 되겠다."

 

"응 맞아 그러면 1037은 소수인지 한번 계산해 볼래?"

 

여러분이 길순이를 대신해서 계산해 주시겠어요?

1037은 소수일까요?

 

정답

1037 / 2 = 518 --- 1

1037 / 3 = 345 --- 2

1037 / 5 = 207 --- 2

1037 / 7 = 148 --- 1

1037 / 11 = 94 --- 3

1037 / 13 = 79 --- 10

1037 / 17 = 61 --- 0

 

따라서 1037은 소수가 아닙니다.