제목: 극대수에서 한번에 소수 찾기
필명: 유전



위 링크의 글에서 이어지는 내용입니다.


소수는 그 끝자리가 1, 3, 7, 9에서만 발견되고 있습니다. 그런데 오일러의 답(파이 제곱 엑스 / 6)에 따라 10이 넘는 수열에서는 나누기 6대신에 6의 배수인 나누기 12를 했을 때 나머지의 값이 1, 5, 7, 11인 경우에만 소수가 자리합니다. 따라서 극대수의 수열이라도 그 끝자리가 1, 3, 7, 9로 끝나는 수만을 먼저 찾고 다시 " 12제곱 X "로 나누었을 때 나머지의 수가 1, 5, 7, 11로 끝나지 않는다면 소수가 아니라고 정의하겠습니다.


예를 들어, 31, 33, 37, 39에서 31은 7, 33은 9, 37은 1, 39는 3이 남기 때문에 이 중에서 1, 5, 7, 11 중에 속한 31과 37은 소수이고 33과 39는 소수가 아닙니다.


---


유전  2017.03.27. 19:33


위와 같은 현상이 발생하는 원인을 가장 간단히 설명하자면, 10진법의 수열을 12진법으로 나누었을 때 그 나머지의 값이 1부터 12(36 = 24 + 나머지 12)까지 있을 수 있는데 그 나머지의 값이 3진법에 수렴되는 3, 6, 9, 12라면 당연히 소수가 될 수 없고 2, 4, 6, 8, 10, 12의 나머지 값은 12+2, 12+4, 12+6...등과 같이 역시나 짝수여서 처음부터 짝수를 배제한 알고리즘의 시작과 함께 1, 5, 7, 11로 남는 수는 2의 배수인 짝수가 아니며 3으로도 나누어지지 않는 소수일 가능성만 남습니다.


따라서 처음부터 2와 3의 배수로 소수를 찾는 일이 불필요하고 5의 배수도 배제된 10진법의 1, 3, 7, 9로 끝나는 수에서 12로 나누었을 때 그 나머지의 값이 1, 5, 7, 11에 해당되는 수만 7, 11, 13, 17... 등의 소수로 나누어질 수 있는지의 여부만 확인하는 알고리즘을 짠다면 한번에 모든 소수를 차례대로 가장 빠르게 찾을 수 있게 됩니다.


---


리만가설.jpg





  • 구글
  • 카카오
  • 싸이월드 공감
  • 추천
  • 인쇄


List of Articles
번호 제목 글쓴이 날짜 조회수sort
공지 [공지] 자유게시판 글쓰기 중단 안내 사이언스온 2020-09-15 209257
153 [타운미팅] 최종 정책 제안집 확인해보셨나요? imagefile 사이언스온 2012-12-11 23725
152 [정보] 전문성의 정치와 민주주의 -국제워크숍 imagefile 오철우 2011-07-13 24321
151 (알림) 서비스 안정화를 위한 서버 점검 admin 2011-07-20 24846
150 [올해의 과학책 이벤트 응모] 신입생에게 추천하고 싶은 과학책 ds5pnz 2012-01-12 25267
149 외계인(UFO) 올수도 있다 gber20 2012-09-10 25267
148 과총이 이공계대학생 과학기술동아리를 지원하네요 image 오철우 2011-08-01 25460
147 '과학관에서 1박2일' 과천과학관 행사 접수 imagefile 사이언스온 2013-07-15 25518
146 서울대 연구진실성위 "안철수 논문 본조사 필요성 없다" 결론 water77 2012-11-16 25583
145 "나로호 3차발사, 내달 26~31일 추진' -교과부 water77 2012-09-11 25742
144 [단신] 정부부처 내년 R&D예산 16조9249억원 요구 사이언스온 2011-07-08 25747
143 [단신] 과천과학관: 여름 자유탐구여행 참가자 모집 사이언스온 2011-07-08 25960
142 문진아카데미, 1기 수강생 모집 (과학커뮤니케이션) 사이언스온 2013-06-18 26044
141 파란 하늘 보고파 imagefile [1] rarabok 2012-08-30 26117
140 (정보) 영국 정부 기후변화 보고서 나왔네요 imagefile 오철우 2011-07-15 26219
139 힉스입자 존재하지 않을수도 있다 [2] gber20 2012-10-24 26392
138 '쓰레기 DNA'의 재발견 사이언스온 2012-09-07 26405
137 겨울 초입... 서리 내린 철쭉 imagefile 사이언스온 2012-11-12 26436
136 힉스 두종류로 나타난 이유(힉스 최종 결론) [3] gber20 2013-06-08 26551
135 [올해의 과학책 이벤트] 당첨자 발표합니다 hanispecial 2012-02-01 26588
134 쌍둥이역설 오류 imagefile 유전 2016-05-26 26601
자유게시판 너른마당

인기글

최근댓글

트위터 팔로우

sub2 untitled