素因数分解もういっかい

• 素因数分解: ツムジのひとりごと
  • ありがとうございます。111111111の計算に48秒もかかるのは私のミスです。factorizeの終了条件に[< n (expt p 2)]が抜けていたのが原因です。お見苦しいコードをお見せしました。

(use util.stream)
(define (composites s)
  (stream-delay
   (let1 p (stream-car s)
     (stream-cons (expt p 2)
                  (xor (stream-map (pa$ * p) (xor (stream-cdr s) (composites s)))
                       (composites (stream-cdr s)))))))

(define (xor s0 s1)
  (stream-delay
   (let ((x (stream-car s0))
         (y (stream-car s1)))
     (cond
      ((= x y) (xor (stream-cdr s0) (stream-cdr s1)))
      ((< x y) (stream-cons x (xor (stream-cdr s0) s1)))
      ((> x y) (stream-cons y (xor s0 (stream-cdr s1))))))))

(define primes (stream-cons 2 (xor (stream-iota -1 3) (composites primes))))

(define (divisor n m count)
  (if (zero? (modulo n m))
    (divisor (quotient n m) m (+ 1 count))
    (values n count)))

(define (factorizer n strm)
  (let loop ([n n] [strm strm] [l '()])
    (let ((p  (stream-car strm))
          (ps (stream-cdr strm)))
      (cond 
       ([= n 1]          (reverse l))
       ([< n (expt p 2)] (reverse (cons (cons n 1) l)))
       (else
        (receive (r count) (divisor n p 0)
          (if (zero? count)
            (loop r ps l)
            (loop r ps (cons (cons p count) l)))))))))

(define (main args)
  (print (factorizer (string->number (cadr args))
                     primes)))

% time gosh factStrm.scm 111111111
((3 . 2) (37 . 1) (333667 . 1))
gosh factStrm.scm 111111111  0.10s user 0.01s system 96% cpu 0.111 total

以上です。

素数ストリームを使う時点で速さは諦めていますが、きれいに書けるので好きです。
ツムジさんのコードは速くてすばらしいです。

• 自分用メモ:ツムジさんのコードを俺流に書いたもの。記録のため残す。

(define (divisor n m count)
  (if (zero? (modulo n m))
    (divisor (quotient n m) m (+ 1 count))
    (values n count)))

(define (factorize n)
  (let loop ([n n] [i 2] [l '()])
    (receive (r count) (divisor n i 0)
      (cond
       ([= n 1]          (reverse l))
       ([> (expt i 2) n] (reverse (cons (cons n 1) l)))
       (else             (loop r
                               (+ i (if (= i 2) 1 2))
                               (if (zero? count)
                                 l
                                 (cons (cons i count) l))))))))

(define (main args)
  (print (factorize (string->number (cadr args)))))

(追記 2009/5/31)
factorizerはstrmを受け取る汎用性があるので、ツムジさんのように素数列を求めずに"2と奇数列"でやるときは、こうします。

(define (main args)
  (print (factorizer (string->number (cadr args))
                     (stream-cons 2 (stream-iota -1 3 2)))))