Hatena::Groupcadr

わだばLisperになる このページをアンテナに追加 RSSフィード

2004 | 12 |
2005 | 01 | 02 | 07 | 10 | 11 |
2006 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 11 |

2007-03-20

L-99 (35)

| 22:38 | L-99 (35) - わだばLisperになる を含むブックマーク はてなブックマーク - L-99 (35) - わだばLisperになる

L-99 35問目に挑戦 - L-99:Ninety-Nine Lisp Problems

P35

解答
;; Common Lisp
(load "is-prime")

(defun prime-factors (n)
  (flet ((next-prime (n)
	   (do ((i (1+ n) (1+ i)))
	       ((is-prime i) i))))
    (labels ((prime-factors1 (n i)
	       (multiple-value-bind (q r)
		   (floor n i)
		 (cond ((< n 2)
			`(,n))
		       ((zerop r)
			(if (= q 1)
			    `(,i)
			    `(,i ,@(prime-factors1 q i))))
		       ('t 
			(prime-factors1 n (next-prime i)))))))
      (prime-factors1 n 2))))

;; Scheme
(load "is-prime")

(define prime-factors
  (lambda (n)
    (let ((next-prime
	   (lambda (n)
	     (let loop ((i (+ n 1)))
	       (if (is-prime i)
		   i
		   (loop (+ i 1)))))))
      (letrec ((prime-factors1
		(lambda (n i)
		  (let ((q (quotient n i))
			(r (remainder n i)))
		    (cond ((< n 2)
			   `(,n))
			  ((zero? r)
			   (if (= q 1)
			       `(,i)
			       `(,i ,@(prime-factors1 q i))))
			  (else
			   (prime-factors1 n (next-prime i))))))))
	(prime-factors1 n 2)))))

今回は素因数分解する関数の作成が課題。色々なアルゴ

リズムはあれど、実装できないので、単純に力ずくで割

り算していくだけの方式で作成。

自分で作っていて自分でも良く分からないものがで

きた。力ずく故に

(prime-factors 99999999999)⇒(3 3 21649 513239)

位で結果が出るまでにしばらく時間がかかる。

まあ、良しとして先に進もう(´Д`)