KAIST 단일서비스 로그인
Language

생활정보(이전)


> 정보 > 생활정보(이전)

042-350-2071

통화 가능 시간

평일 13:00-17:00

메일 | 건의게시판

?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄 수정 삭제 스크랩
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄 수정 삭제 스크랩

안녕하세요. 연구하느라 바쁜 와중에도 짬짬이 남는 시간에 포스팅을 하려고 하지만 결국 그 남는 시간에는 술을 마시거나 롤을 하는 바람에 3주만에 포스팅을 하게 된 독거노인입니다. 바쁜 와중에도 꾸준히 포스팅을 하는 다른 대학원생 능력자 K 분들이 새삼 존경스럽게 느껴지네요.

 
저번 포스팅에서 얘기드렸던 7,11,13 의 배수판별법은 까먹지 않으셨나요? 너무 오랜만에 글을 올려 잊어버린 분들이 많으실 것 같은데, 뒤의 세자리 숫자에서 앞의 천의자리숫자를 뺀 수(abcd 의 경우 bcd -a)가 7 또는 11 또는 13의 배수이면 원래의 숫자도 7 또는 11 또는 13의 배수가 된다는 내용이었습니다. 올해 2015 년의 경우 15 -2 = 13 이 나오니까 2015가 13의 배수라는 걸 쉽게 판별할 수 있겠죠. 이를 이용하면 2015 = 5x13x31이라는 걸 쉽게 계산할 수가 있습니다.

오늘은 이제 남은 과제인 배수판별법이 없는 17 이상의 소수에 대해 어떤 식으로 판별이 가능한지에 대해 얘기하고자 합니다. 배수판별법이 존재하는 2,3,5,7,9,11,13 의 경우에는 사실 원리만 알면 누구나 쉽게 판별이 가능하고 판별이 된 이후부터는 단순 계산 문제가 됩니다. 개인적으로 이 부분을 처리하는 속도에 있어서는 고등학교 때에 비해 나아진 점이 딱히 없는 것 같습니다. 오히려 술을 덜 마셨던 고등학교 때가 더 빠르지 않았나 하는 생각도 들고요. 하지만 17 이상부터는 case by case 로 접근을 해야 하고 이때부터는 하드웨어보다는 소프트웨어,즉 경험에서 우러나온 노련미가 중요해지게 됩니다. 개인적으로 앞으로도 계속 발전해나갈 여지가 있다고 여겨지는 부분이기도 하고요. 
 
첫번째 말씀드릴 것은 확률적인 문제입니다. 17 이후의 소수들의 경우 약수가 될 확률이 매우 낮습니다. 17의경우  1/17, 19의 경우 1/19, 수가 올라가면 올라갈수록 더욱 더 확률은 낮아지게 되겠죠. 주어진 숫자가 x 라고 했을때 x 의 제곱근까지 약수를 찾지 못하면 주어진 수는 소수라고 결론을 내릴 수 가 있게 되는데요, 4자리 숫자는 최악의 경우 17 부터 97까지 체크를 해봐야 합니다. 이런 과정은 몹시 지루하다 보니 의욕이 꺽이기 쉬운데요 그러다보니 저도 어린 시절엔 적당히 나눠보다 안되면 그냥 소수! 라고 외치곤 했습니다. 어짜피 물어보는 사람도 알 리가 만무하거든요.
 
하지만 과학의 발전의 부작용으로 소인수분해를 즉각적으로 해주는 해괴망측한 사이트들이 생겨났고, 적당히 하다 안 되면 소수!라고 외치던 전략은 저에게 창피를 안겨주기 시작했습니다. 억지로 소수 두개를 곱한 73x89 같은 더러운 숫자를 만들어내서 저를 괴롭히던 한xx 선배가 생각나는군요. 결국 이제는 시대적 상황이 끝까지 나눠보지 않으면 인정을 받을 수 없는 지경까지 와버렸습니다.
 
여하튼간에 우리의 당면 과제는 17~97 에 해당하는 소수들에 대하여 주어진 수의 약수인지 아닌지 여부를 빠르게 판별하는 것입니다. 가장 시간을 많이 잡아먹게 되는 부분이며 그렇기에 가장 중요한 부분이라고 할 수 있습니다.
 
다행인 점은 우리가 17~97 까지의 소수들에 대하여 원래의 수를 나눈 각각의 몫과 나머지를 계산할 필요는 없다는 점입니다. 첫번쨰 포스팅에서도 얘기했지만 나누어 떨어지는지 아닌지 여부만 알면 됩니다. 달리 말하면 주관식이 아니라 객관식 그것도 이지선다형이라는 얘기입니다. 물론 나누어 떨어지는 순간 주관식 단답형이 되겠지만 나누어 떨어지는 것도 감사할 노릇이니까 그 점에 대해서는 불평불만 가지지 마세요. 나누어 떨어지지 않는 경우엔 재빠르게 다음 소수로 넘어가면 되겠죠.
 
그렇다면 어떻게 하면 몫과 나머지를 계산하지 않고도 빠르게 나누어떨어지는지 아닌지 여부를 판별할 수 있을까요? 일반적으로 소인수분해를 하는 사람들이 주로 쓰는 방법은 글쎄요, 제가 아는 사람 중엔 그런 사람이 저밖에 없어서 제 방법을 말씀드릴 수 밖에 없을 것 같습니다. 숫자에 따라 이런 저런 방법을 쓰곤 하는데 본질은 단순한 유클리드 호제법입니다. 정수론을 더 공부해서 좀 더 고급 이론들을 적용하고 싶은 욕심도 있긴 한데 우리 동네 수학도 잘 못하는데 옆 동네 수학까지 건드릴 엄두가 나질 않네요.

 
유클리드 호제법에 대해서 좀 더 얘기해보도록 하겠습니다. 일반적인 유클리드 호제법은 G.C.D(최대공약수) 에 관한 이야기지만 저희는 최대공약수까지는 관심이 없으므로 나누어떨어지는 여부에 대해서만 촛점을 맞추면, "a 가 p 의 배수인지 아닌지는 a+p 가 p 의 배수인지 아닌지와 동치이다" 라고 기술할 수 있습니다. 좀 더 일반화를 시키면 임의의 정수 k 에 대하여 "a 가 p 의 배수인지 아닌지는 a+kp 가 p 의 배수인지 아닌지와 동치이다" 라고도 기술할 수 있겠네요. 결국 될 놈은 되고 안 될 놈은 안된다는 게 유클리드 호제법의 본질이라고 볼 수 있습니다.
 
그렇다면 유클리드 호제법이 어떻게 약수판별에 도움을 줄 수 있는지 나름대로 예를 들어가며 기술해보도록 하겠습니다.
 
여러분이 어떤 한 종류의 레고로 집을 지었는데 이 집을 짓는데 쓰인 레고의 갯수가 17의 배수인지 아닌지가 알고 싶다고 합시다. 가장 간단한 방법은 레고를 17개씩 계속 떼내는 방법이겠죠. 이렇게 자꾸 떼내다가 더 이상 떼낼 수 없을 때 남은 레고의 숫자가 0이면 나누어 떨어지는 거고 1~16 사이면 안 나누어 떨어지는 거겠죠. 이는 몫과 나머지를 모두 계산하는 방법이라고 생각할 수 있습니다. 실제론 나눗셈도 아니고 무식하게 뺄셈을 n 번 하는 형국이죠.
 
그런데 17개씩 떼내다보니 바닥만 남았는데 남은 바닥 사이즈가 23x19 라고 해봅시다. 그렇다면 굳이 여기서 타일을 더 떼내지 않더라도 가로 23 세로 19 모두 17의 배수는 아니니까 바닥에 사용된 레고의 숫자는 17의 배수가 아니라는 걸 알 수 있습니다. 그렇다면 유클리드 호제법에 의하여 원래 집을 짓는데 사용된 레고의 갯수는 17의 배수가 아니라고 결론을 지을 수 있는 것이죠.
 
반면에 이런 경우도 생각할 수가 있습니다. 지붕 사이즈가 34 x 27 이라고 생각해봅시다. 그렇다면 34는 17의 배수이기 때문에 지붕을 쌓는데 사용된 레고의 갯수는 17의 배수가 되겠죠. 이런 경우엔 굳이 지붕에서 레고 17개씩 떼낼 게 아니라 지붕은 한 방에 뜯어버려도 됩니다. 어짜피 17개씩 계속 떼다 보면 지붕만 쏘옥 떨어져 나갈 테니까요. 지붕을 통째로 때넨 부분이 17의 배수인지 아닌지가 원래 집이 17의 배수인지 아닌지가 같다는 점 역시 유클리드 호제법의 결과라고 볼 수 있습니다.
 
비유가 다소 조약하지만 어쨌든 제가 표현하고자 하는 아이디어가 충분히 전달되었길 바랍니다. 위의 논리에 의하면 효과적으로 유클리드 호제법을 사용하기 위해선 다음과 같은 작업이 필요합니다. 1)어떻게든 지붕처럼 한 번에 떼어낼 수 있는 부분을 잘 떼어내서 2) 바닥처럼 배수여부가 한 눈에 보이는 부분만을 남긴다.
 
그렇다면 위의 아이디어를 레고로 만든 집이 아닌 실제 숫자에는 어떻게 적용을 할 수 있을까요?
 
이는 다음에 이어질 Part2 에서 얘기하도록 하겠습니다.
 
 

 



 

 
  • ?
    2015.04.07 21:03 0/0
    잘봤습니다!
    '결국 될 놈은 되고 안 될 놈은 안된다는 게 유클리드 호제법의 본질이다'
    이 부분이 와닿네요

List of Articles
번호 분류 제목 글쓴이 날짜 조회 수
65 취미 [능력자K/캘리그라피] 2월 좌우명 캘리그라피 이벤트 올립니다. 3 file 백호랑 2015.04.07 1451
64 음악/스포츠 [능력자K/음악] 노다메칸타빌레로 본 오케스트라 뒷이이기(3/3) 2 file 크아홍 2014.12.15 820
63 음악/스포츠 [능력자K/음악] 노다메 칸타빌레로 본 Orchestra 뒷이야기(2/3) file 크아홍 2014.12.12 866
62 음악/스포츠 [능력자K/음악] 노다메 칸타빌레로 본 Orchestra 뒷이야기(1/3) 3 file 크아홍 2014.12.02 882
61 음악/스포츠 [능력자K/음악] 기덕이의 기타이야기 :: 7. 나의 소리를 너에게 더 잘 들려주고 싶어! 픽업이야기!! file 크아홍 2015.02.21 1189
60 음악/스포츠 [능력자K/음악] 기덕이의 기타이야기 :: 6. 어떤 기타를 살 것인가? Tip!! (2/2) file 크아홍 2015.02.04 1086
59 음악/스포츠 [능력자K/음악] 기덕이의 기타이야기 :: 5. 어떤 기타를 살 것인가? Tip!! (1/2) file 크아홍 2015.01.26 874
58 음악/스포츠 [능력자K/음악] 기덕이의 기타이야기 :: 4. All -Solid! 집중 탐구!! 1 file 크아홍 2015.01.23 1099
57 음악/스포츠 [능력자K/음악] 기덕이의 기타이야기 :: 3. 기타의 재질에 대한 탐구 1 file 크아홍 2015.01.15 933
56 음악/스포츠 [능력자K/음악] 기덕이의 기타이야기 :: 2. 단순히 크기가 중요한게 아니야... 4 file 크아홍 2015.01.08 997
55 음악/스포츠 [능력자K/음악] 기덕이의 기타이야기 :: 1. 기타가 뭔지는 아느뇨?? file 크아홍 2014.12.25 923
54 음악/스포츠 [능력자K/음악] 궁금했지만 찾아보지 않았던 "음악"+과학이야기(음과 음색) file 크아홍 2015.02.27 1038
53 여행/사진 [능력자K/여행] 2. 현지인집에서 '무료' 숙박 카우치서핑 (Couchsurfing) vs 현지인집을 '임대'하는 에어비앤비 (Airbnb) file 감자 2015.02.16 1155
52 여행/사진 [능력자K/여행] 1. 현지인 집에서 숙박을 해결한다구? 7 file 감자 2014.12.21 1150
51 여행/사진 [능력자K/여행] 0. Intro. 열심히 연구한 우리, 떠나자! 1 감자 2014.12.20 914
50 취미 [능력자K/소인수분해]3. Main Dish (Part2) 2 독거노인 2015.02.21 969
» 취미 [능력자K/소인수분해]3. Main Dish (Part1) 1 독거노인 2015.01.25 951
48 취미 [능력자K/소인수분해] 2.배수판별법 2 독거노인 2014.12.31 2080
47 취미 [능력자K/소인수분해] 1. 동기 부여 14 독거노인 2014.12.15 8095
46 결혼/뷰티 [능력자K/뷰티][피부지키기 클렌징편] 남 : 클렌징은 뽀독뽀독해야 씻은거같지! 여 : 이중세안을 꼭 해야 화장이 잘 지워지지! file ccomziracrac 2015.02.18 1078
Board Pagination 1 ... 4 5 6 7 8 9 10 11 12 ... 13
/ 13