# 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
17      m n lin)
18 (dotimes (i cnt)
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)