알라딘MGG와이드바


Clojure - Prime Wheel (!= Prime Gap) 개발 이야기

오늘 clojure 스터디를 하다가 소수를 구하는 코드를 봤는데 처음 보는 숫자들을 이용하고 있어서 찾아보았다. 먼저 clojure 의 Primes 코드는 다음과 같다. (Referenced Libraries -> clojure-contrib.jar -> clojure.contrib -> lazy_seqs.clj)


   1: (ns your-namespace  
   2: (:use clojure.contrib.def)) 
   3:  
   4: ; (take-while #(<= (* % %) n) primes)
   5: ; AAA : 지금까지 확인된 소수 중에서 제곱값이 n 값보다 작은 수들을 모아서 seq 리턴
   6: ; (some #(zero? (rem n %)) AAA)
   7: ; 하나라도 나눠지는게 있다면(즉, n 이 소수가 아니라면..)
   8: ; (recur (+ n f) r)
   9: ; n 에 f (Prime Wheel)을 더한 값으로 넘어간다.
  10: ; (lazy-seq (cons n (primes-from (+ n f) r)))
  11: ; 소수니까 cons 로 합쳐준다.
  12: ; Wheel 은 Prime Wheel 을 의미한다.
  13: (defvar primes
  14:     (concat 
  15:         [2 3 5 7]
  16:         (lazy-seq
  17:             (let [
  18:                 primes-from (fn primes-from [n [f & r]]
  19:                     (if (some #(zero? (rem n %)) (take-while #(<= (* % %) n) primes))
  20:                         (recur (+ n f) r)
  21:                         (lazy-seq (cons n (primes-from (+ n f) r)))
  22:                     )
  23:                 )
  24:                 wheel (cycle [
  25:                       2 4 2 4 6  2 6  4 2 4
  26:                       6 6 2 6 4  2 6  4 6 8
  27:                       4 2 4 2 4  8 6  4 6 2
  28:                       4 6 2 6 6  4 2  4 6 2
  29:                       6 4 2 4 2 10 2 10]
  30:                     )
  31:                 ]
  32:                 (primes-from 11 wheel)))    ; 11 부터 소수를 찾아라
  33:     )
  34:     "Lazy sequence of all the prime numbers."
  35: )
  36:  
  37: (nth primes 10)


[http]에라토스테네스의 체 Sieve of Eratosthenes 을 쓰는 거 같긴 한데 숫자 2 4 2 4 6 2 6 4 2 4 ... 이게 뭔가 하고 찾아봤더니 처음에는 [http]wikipedia - Prime Gap 이 나오더라. 그런데 뒤로 갈수록 조금씩 숫자가 달라져서 고민하고 있었는데 알고 보니 Prime Wheel 을 표헌한 것이었다.

모든 정수는 6k + m (m ε {0, 1, 2, 3, 4, 5} 이고 k 는 임의의 정수) 라고 표현할 수 있다. 그러면 다음과 같이

m=0: 6k 은 6으로 나뉜다. 소수 아님
m=1: 6k+1 소수일지도 모른다
m=2: 6k+2 = 2 x (3k+1). 소수 아님
m=3: 6k+3 = 3 x (2k+1). 소수 아님
m=4: 6k+4 = 2 x (3k+2). 소수 아님
m=5: 6k+5 소수일지도 모른다

6k + 1, 또는 6k + 5 만이 소수가 될 가능성이 있다는 것을 알 수 있다. 이런 것을 소수바퀴(Prime Wheel)라고 한다. 원주 6짜리 바퀴의 1 과 5에 도장을 박아놓고 정수축을 따라서 바퀴를 굴리면 소수가 될 가능성이 있는 숫자에만 도장이 찍힌다는 의미로 Prime Wheel 이라는 용어를 쓰는 듯 하다.

clojure 의 primes 에서는 미리 2 3 5 7 이라는 소수를 구한 뒤, 2 * 3 * 5 * 7 = 210 짜리 커다란 Prime Wheel 을 만들어 쓰고 있다. 즉, 모든 정수를 210k + m(0 <= m < 210) 으로 표현할 때 소수가 분명 아닌 정수는 다음과 같다.

m=0: 210k is divisible by 210. 소수 아님
m=1: 210k+1 소수일지도 모른다
m=2: 210k+2 = 2 x (105k+1). 소수 아님
m=3: 210k+3 = 3 x (70k+1). 소수 아님
m=4: 210k+4 = 2 x (105k+2). 소수 아님
m=5: 210k+5 = 5 x (42k+1). 소수 아님
m=6: 210k+6 = 2 x (105k+3). 소수 아님
m=7: 210k+7 = 7 x (30k+1). 소수 아님
m=8: 210k+8 = 2 x (105k+4). 소수 아님
m=9: 210k+9 = 3 x (70k+3). 소수 아님
m=10: 210k+10 = 2 x (105k+5). 소수 아님
m=11: 210k+11 소수일지도 모른다 (10)
m=12: 210k+12 = 2 x (105k+6). 소수 아님
m=13: 210k+13 소수일지도 모른다 (2)
m=14: 210k+14 = 2 x (105k+7). 소수 아님
m=15: 210k+15 = 3 x (70k+5). 소수 아님
m=16: 210k+16 = 2 x (105k+8). 소수 아님
m=17: 210k+17 소수일지도 모른다 (4)
m=18: 210k+18 = 2 x (105k+9). 소수 아님
m=19: 210k+19 소수일지도 모른다 (2)
m=20: 210k+20 = 2 x (105k+10). 소수 아님
m=21: 210k+21 = 3 x (105k+7). 소수 아님
m=22: 210k+22 = 2 x (105k+10). 소수 아님
m=23: 210k+23 소수일지도 모른다 (4)
m=24: 210k+24 = 2 x (105k+11). 소수 아님
m=25: 210k+25 = 5 x (42k+5). 소수 아님
m=26: 210k+26 = 2 x (105k+12). 소수 아님
m=27: 210k+27 = 3 x (70k+9). 소수 아님
m=28: 210k+28 = 2 x (105k+13). 소수 아님
m=29: 210k+29 소수일지도 모른다 (6)
m=30: 210k+30 = 2 x (105k+14). 소수 아님
....

괄호 안에 있는 숫자가 Prime Wheel 에 들어갈 숫자다. 우리는 11 부터 소수를 찾기 때문에 Prime Wheel 은 2 4 2 4 6 2 6 이 들어가게 된다. Wheel 에 있는 값을 전부 더하면 Prime Wheel 의 원주라고 할 수 있는 210 이 나온다.

지금까지 스터디에서 알고리즘 공부할 때를 제외하고 소수(Prime Number) 생성기 프로그램을 짤 일은 없었다. 하지만 바로 그런 이유 때문에 스터디를 하는 것이다. 하던대로 일하다보면 다른 분야나 다른 방식으로 머리를 쓸 일이 점점 없어져서 요령대로 적당히 일하게 되는 경우가 많은데 스터디를 하다보면 안 쓰던 두뇌 근육을 단련시킬 수 있다. [http]Sieve of Atkin 라고 더 좋은 알고리즘도 있다던데 언제 살펴볼 수 있을런가...

(제가 놓치는 부분이 있을 듯 한데 댓글로 도와주시면 감사하겠습니다)

[http]Prime numbers From HaskellWiki
[http]Everything2 All primes greater than 3 are of the form 6k-1 or 6k+1
[http]erlang - concurrent prime generator
[http]cs.cmu.edu - Primes
[http]stack-overflow Concurrent Prime Generator
[http]Implementing the sieve of Eratosthenes using channels in Go


덧글

댓글 입력 영역


Yes24위대한게임의탄생3

위대한 게임의 탄생 3
예스24 | 애드온2