リスト修行動的に素数を生成したい。

前回は、12の素因数分解をするときに、2〜12までのリストを作成し、それから素因数分解をしました。しかし、12が必要とする素数は2と3だけ。12までふるいをかけるのは無駄です。しかも、ふるいが重い!!

そんなわけで、素数が必要となってから、素数を生成したい。つまり、

「動的に素数リストを生成したい」

ムズそう・・・とか思ったけど

foldで

あっさり出来ちゃいました。

(define (primers-filter n p)
  (remove
    (lambda (x)
      (zero? (modulo x n)))
    p))

(define (make-primers p)
  (fold-right
    (lambda (a b)
      (primers-filter a b))
    (iota (car p) (+ (car p) 1))
    p))

これだけ。

ポイントは、fold-rightで、これからふるいにかけるリストを生成し、今まで作った素数リストでフィルタリング。foldは二つのリストから新たなリストを作る事ができるんですね。

リストが逆順になっていた方が今後の効率が良さそうなので入力を逆順にしてみました。

(生成は2乗分まで可能ですが、途中でキャッシュがヒットした時、無駄が多い。とりあえず2倍)

するっと、

(make-primers '(2)) ; (3)
(make-primers '(3 2)) ; (5)
(make-primers '(5 3 2)) ; (7)
(make-primers '(7 5 3 2)) ; (11 13)
(make-primers '(13 11 7 5 3 2)) ; (17 19 23)
(make-primers '(23 19 17 13 11 7 5 3 2)) ; (29 31 37 41 43)

動的に素数を生成出来ました。キャッシュが空になったら、make-primersするだけです。

キャッシュを作る→キャッシュを消費→キャッシュを作る→キャッシュを消費....

という作戦です。動的っしょ?

素因数分解してみよう。

ちょっと変更を加えます。

(define (factor n)
  (define (factor-iter m p1 p2)
    (define (next p)
      (factor-iter m (cons (car p) p1) (cdr p)))
    (cond ((= m 1) '())
          ((zero? (modulo m (car p1)))
           (cons (car p1)
                 (factor-iter (/ m (car p1)) p1 p2)))
          ((null? p2)
           (next (make-primers p1)))
          (else
            (next p2))))
  (factor-iter n '(2) '()))

nextで、キャッシュから一個popして、素数リストにpushするように変更を加えました。

テストぉ〜

(factor 1) ; ()
(factor 11) ; (11)
(factor 111) ; (3 37)
(factor 1111) ; (11 101)
(factor 11111) ; (41 271)
(factor 111111) ; (3 7 11 13 37)
(factor 1111111) ; (239 4649)
(factor 11111111) ; (11 73 101 137)

次は・・・・大きな素数が入っているので止めた方が良さげ。

かなり速度アップです。

とんでもないモノを作ちゃったみたい

自分で作ってびっくりなのですが、物凄い素因数分解力を持っている様子。

(factor 1461501637330902918203684832716283019655932542976)
; (2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ....

小さな素数の組み合わせなら、一瞬で素因数分解出来ちゃいます。驚きです。

課題

大きな素数が現れた時の素因数分解には激しく弱いので、改善していきたいかな・・・。

追記

改善しました。

13だったら、5(ルート13の次の素数)まで見れば、素数だと確定出来る。

(sqrt 13) ; 3.605551275463989

1行加えると。

          ((< m (* (car p1) (car p1)))
           (cons m '()))

実験。

(factor 1) ; ()
(factor 11) ; (11)
(factor 111) ; (3 37)
(factor 1111) ; (11 101)
(factor 11111) ; (41 271)
(factor 111111) ; (3 7 11 13 37)
(factor 1111111) ; (239 4649)
(factor 11111111) ; (11 73 101 137)
(factor 111111111) ; (3 3 37 333667)
(factor 1111111111) ; (11 41 271 9091)
(factor 11111111111) ; (21649 513239)
(factor 111111111111) ; (3 7 11 13 37 101 9901)
(factor 1111111111111) ; (53 79 265371653)
(factor 1) ; ()
(factor 12) ; (2 2 3)
(factor 123) ; (3 41)
(factor 1234) ; (2 617)
(factor 12345) ; (3 5 823)
(factor 123456) ; (2 2 2 2 2 2 3 643)
(factor 1234567) ; (127 9721)
(factor 12345678) ; (2 3 3 47 14593)
(factor 123456789) ; (3 3 3607 3803)
(factor 1234567890) ; (2 3 3 5 3607 3803)
(factor 12345678901) ; (857 14405693)
(factor 123456789012) ; (2 2 3 10288065751)
(factor 1234567890123) ; (3 3541 116216501)
(factor 12345678901234) ; (2 7 73 12079920647)
(factor 123456789012345) ; (3 5 283 3851 7552031)
(factor 1234567890123456) ; (2 2 2 2 2 2 3 7 7 301319 435503)

おぉ、すげぇ。

かなりfactor(コマンド)に近づいてきた。

約数

忘れてた。僕の目的は約数を求めることだった。

(factor 1234567890) ; (2 3 3 5 3607 3803)
(divisor 1234567890)
; (1 2 3 5 6 9 10 15 18 30 45 90 3607 3803 7214 7606 10821 11409 18035
;  19015 21642 22818 32463 34227 36070 38030 54105 57045 64926 68454 108210
;  114090 162315 171135 324630 342270 13717421 27434842 41152263 68587105
;  82304526 123456789 137174210 205761315 246913578 411522630 617283945 1234567890)

圧巻ですねぇ。

キャッシュをあらかじめ作っておくと劇速っす。