coreBugZJ

此 blog 已弃。

PRIME1 - SPOJ 2. Prime Generator

版本三终于 AC 了。

LISP SBCL

1(defconstant +max-size+ 35000)
2(defvar *prime* (make-array +max-size+ :initial-element t))
3(defvar *prime-size* 0)
4
5(defun init-prime()
6 (do
7 ((i 2 (1+ i)))
8 ((>= i +max-size+))
9 (when (elt *prime* i)
10 (setf (elt *prime* *prime-size*) i)
11 (incf *prime-size*)
12 (do
13 ((j (+ i i) (+ j i)))
14 ((>= j +max-size+))
15 (setf (elt *prime* j) nil)))))
16
17(defconstant +max-len+ 100009)
18(defvar *ans* (make-array +max-len+ :initial-element t))
19(defvar *ans-size*)
20
21(defun solve(m n)
22 (when (< m 2) (setf m 2))
23 (when (> m n)
24 (format t "~%")
25 (return-from solve nil))
26 (setf *ans-size* (1+ (- n m)))
27 (dotimes (i *prime-size*)
28 (let* ((p (elt *prime* i))
29 (b (* (floor (/ (1- (+ m p)) p)) p)))
30 (do ((x (if (> b p) b (+ p p)) (+ x p)))
31 ((> x n))
32 (setf (elt *ans* (- x m)) nil))))
33 (dotimes (i *ans-size*)
34 (if (elt *ans* i)
35 (format t "~d~%" (+ m i))
36 (setf (elt *ans* i) t)))
37 (format t "~%" ))
38
39(init-prime)
40(let ((cnt (parse-integer (read-line)))
41 m n lin)
42 (dotimes (i cnt)
43 (setf lin (read-line))
44 (setf m (parse-integer (subseq lin 0 (position #\Space lin))))
45 (setf n (parse-integer (subseq lin (1+ (position #\Space lin)))))
46 (solve m n)))
47

posted on 2012-02-06 16:06 coreBugZJ 阅读(336) 评论(0)  编辑 收藏 引用 所属分类: ACM 、Lisp


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理