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
    잘봤습니다!
    '결국 될 놈은 되고 안 될 놈은 안된다는 게 유클리드 호제법의 본질이다'
    이 부분이 와닿네요

  1. [능력자K/소인수분해]3. Main Dish (Part1) [1]

    Date2015.01.25 Category취미 By독거노인 Views953
    Read More
  2. 끊임없이 나오는 일품한정식 요리 만년동 [대나무통밥맛정식 죽향] [1]

    Date2015.01.25 Category식도락 By비정상의장 Views1862
    Read More
  3. [능력자K] :::월평생고기::: 맛있는 고기와 미친 쌈 영접 가능. [4]

    Date2015.01.23 Category식도락 By행행나♥ Views1394
    Read More
  4. [홈베이킹] 초코칩쿠키 재료의 효과에 대한 탐색적 연구 – 버터와 설탕을 중심으로 : Discussion / Conclusion [2]

    Date2015.01.23 Category취미 By Views1164
    Read More
  5. [홈베이킹] 초코칩쿠키 재료의 효과에 대한 탐색적 연구 – 버터와 설탕을 중심으로 : Discussion / Conclusion [0]

    Date2015.01.23 By Views452
    Read More
  6. [능력자K/음악] 기덕이의 기타이야기 :: 4. All -Solid! 집중 탐구!! [1]

    Date2015.01.23 Category음악/스포츠 By크아홍 Views1101
    Read More
  7. [능력자K] 어떤 펀드가 좋은 펀드일까요? (2편) [2]

    Date2015.01.20 Category취미 Bykwon4711 Views909
    Read More
  8. [능력자K] Extra 2% : 꼴등을 일등으로 만드는 머니볼의 이해 [9]

    Date2015.01.19 Category음악/스포츠 By쿨럭 Views1053
    Read More
  9. [능력자K]:::임진강 장어::: 대전 장어집 중 TOP에 들만 한 곳. [5]

    Date2015.01.19 Category식도락 By행행나♥ Views1652
    Read More
  10. [능력자K/뷰티][젊게살기:노화방지편] 유일하게 FDA에서 승인한 노화방지제가 있다구? [4]

    Date2015.01.18 Category결혼/뷰티 Byccomziracrac Views1151
    Read More
  11. [능력자K/결혼] EP03_결혼 준비 시작! One time, only에 속지 말자. (1/2) [6]

    Date2015.01.18 Category결혼/뷰티 By새댁 Views1141
    Read More
  12. [능력자K/음악] 기덕이의 기타이야기 :: 3. 기타의 재질에 대한 탐구 [1]

    Date2015.01.15 Category음악/스포츠 By크아홍 Views936
    Read More
  13. [능력자K/뷰티] [젊게살기:탈모예방편] 하아… 내 머리… [3]

    Date2015.01.14 Category결혼/뷰티 Byccomziracrac Views1123
    Read More
  14. [능력자K/캘리그라피] 이벤트 - "당신의 좌우명을 알려주세요" [20]

    Date2015.01.14 Category취미 By백호랑 Views1017
    Read More
  15. [홈베이킹] 초코칩쿠키 재료의 효과에 대한 탐색적 연구 – 버터와 설탕을 중심으로 : Discussion / Conclusion [0]

    Date2015.01.13 By Views121
    Read More
  16. [능력자 K] :::어은스시::: 바로 옆에 생긴 스시집에 대한 정말 솔직한 후기 [11]

    Date2015.01.13 Category식도락 By행행나♥ Views2087
    Read More
  17. [홈베이킹] 초코칩쿠키 재료의 효과에 대한 탐색적 연구 – 버터와 설탕을 중심으로 : Result/Assessment [6]

    Date2015.01.13 Category취미 By Views1196
    Read More
  18. [능력자K] :::해남해산물::: 싱싱한 해산물 덕에 술이 들어가는 곳 [1]

    Date2015.01.12 Category식도락 By행행나♥ Views1225
    Read More
  19. [능력자K] 무엇이 유망주 투수를 망가뜨리는가 : 버두치 효과 [5]

    Date2015.01.12 Category음악/스포츠 By쿨럭 Views1076
    Read More
  20. [홈베이킹] 초코칩쿠키 재료의 효과에 대한 탐색적 연구 – 버터와 설탕을 중심으로 : Introduction/Method [6]

    Date2015.01.08 Category취미 By Views1361
    Read More
Board Pagination 1 ... 4 5 6 7 8 9 10 11 12 ... 13
/ 13

포인트랭킹

순위
닉네임
포인트
1
카이**
5699
2
서**
5005
3
봐*
4810
4
동**
3897
5
대학원****
2414