# coreBugZJ

## PRIME1 - SPOJ 2. Prime Generator

Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers!

### Input

The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.

### Output

For every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line.

### Example

```Input:
2
1 10
3 5

Output:
2
3
5
7

3
5
```
Warning: large Input/Output data, be careful with certain languages (though most should be OK if the algorithm is well designed)

LISP SBCL

1 (defun primep(n)
2 (when (< n 2) (return-from primep NIL))
3 (when (= n 2) (return-from primep T))
4 (let ((m (floor (sqrt n))) (i 2))
5 (loop
6 (when (> i m) (return-from primep T))
7 (when (zerop (rem n i)) (return-from primep NIL))
8 (incf i))))
9 10 (defun solve(m n)
11 (do ((p m (1+ p)))
12 ((> p n))
13 (when (primep p) (format t "~d~%" p)))
14 (format t "~%"))
15 16 (let ((cnt (parse-integer (read-line)))
17 m n lin)
18 (dotimes (i cnt)
19 (setf lin (read-line))
20 (setf m (parse-integer (subseq lin 0 (position #\Space lin))))
21 (setf n (parse-integer (subseq lin (1+ (position #\Space lin)))))
22 (solve m n)))
23 24 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 (defun primep(n)
18 (when (< n 2) (return-from primep nil))
19 (when (or (= n 2) (= n 3)) (return-from primep t))
20 (do
21 ((i 0 (1+ i))
22 (p (elt *prime* 0) (elt *prime* (1+ i))))
23 ((or (>= i *prime-size*) (> (* p p) n)) t)
24 (when (zerop (rem n p)) (return-from primep nil))))
25 26 (defun solve(m n)
27 (do ((p m (1+ p)))
28 ((> p n))
29 (when (primep p) (format t "~d~%" p)))
30 (format t "~%"))
31 32 (init-prime)
33 (let ((cnt (parse-integer (read-line)))
34 m n lin)
35 (dotimes (i cnt)
36 (setf lin (read-line))
37 (setf m (parse-integer (subseq lin 0 (position #\Space lin))))
38 (setf n (parse-integer (subseq lin (1+ (position #\Space lin)))))
39 (solve m n)))
40 41 posted on 2012-02-05 17:19 coreBugZJ 阅读(215) 评论(0)  编辑 收藏 引用 所属分类: ACMLisp 