# Scheme:数遊び:素因数分解

Scheme:数遊び:素因数分解

## 素因数分解

gemma(2009/04/20 09:42:57 PDT)

```(use srfi-1)
(define (primes n)
(cond
((<= n 1) '())
((=  n 2) '(2))
(else
(let loop ((l (unfold (cut > <> n) values (cut + <> 2) 3))
(prime-list '(2)))
(let1 m (car l)
(if (> (expt m 2) n)
(append (reverse prime-list) l)
(loop (remove (lambda (x) (zero? (modulo x m))) l)
(cons m prime-list))))))))

(define (factorize n)
(map (lambda (x)
(cons x (let loop ((n n)
(c 0))
(if (not (zero? (modulo n x)))
c
(loop (quotient n x) (+ c 1))))))
(filter (lambda (x) (and (<= x n) (zero? (modulo n x)))) (primes n))))
```

(factorize 60) outputs ((2 . 2) (3 . 1) (5 . 1))
ストリーム版。素数ストリームは遅くて、せいぜい5万以下の素数までしか実用にならない。一度5万まで計算してしまえば(これがしんどい)、次からは速い。

```(use srfi-1)
(use util.stream)

(define (sieve xs)
(stream-delay (stream-cons (stream-car xs)
(sieve (stream-remove (lambda (n)
(zero? (modulo n (stream-car xs))))
(stream-cdr xs))))))

(define primes (stream-cons 2 (sieve (stream-iota -1 3 2))))

(define (factorize n)
(map (lambda (x)
(cons x (let loop ((n n)
(c 0))
(if (not (zero? (modulo n x)))
c
(loop (quotient n x) (+ c 1))))))
(filter (lambda (x) (zero? (modulo n x))) (stream->list (stream-take-while (cut <= <> n) primes)))))
```

sasagawa?(2010/10/08 17:39:14 PDT)

```;;nを素因数分解して標準形式にして返す。p^a + q^b + r^c ((p a)(q b)(r c))
(define (prime-factors n)
(define (iter ls p n mult)
(cond ((null? ls) (cons (list p n) mult))
((eq? (car ls) p) (iter (cdr ls) p (+ n 1) mult))
(else (iter (cdr ls) (car ls) 1 (cons (list p n) mult)))))
(let ((ls (prime-factors2 n)))
(iter (cdr ls) (car ls) 1 '())))

;;ｍがｎで割り切れるかどうか。割り切れれば#t そうでなければ#f
;; n|m 相当
(define (devidable m n)
(= (modulo m n) 0))

;;nを素因数分解する。指数形式ではなく単純に素数を並べたリストで返す。
;;prime-factorsの下請け
(define (prime-factors2 n)
(define (iter p x ls z)
(cond ((= x 1) ls)
((> p z) (cons x ls))
((devidable x p) (iter1 p (/ x p) (cons p ls)))
((= p 2) (iter 3 x ls z))
(else (iter (+ p 2) x ls z))))
(define (iter1 p x ls)
(if (devidable x p)
(iter1 p (/ x p) (cons p ls))
(iter p x ls (sqrt x))))
(iter 2 n '() (sqrt n)))

gosh> (time (prime-factors 12345678901234567890))
;(time (prime-factors 12345678901234567890))
; real   0.000
; user   0.000
; sys    0.000
((2 1) (3 2) (5 1) (101 1) (3541 1) (3607 1) (3803 1) (27961 1))
```

Tags: Puzzle, util.stream