# 2. Prime Generator

## Problem code: PRIME1

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)
 Added by: Adam Dzedzej Date: 2004-05-01 Time limit: 6s Source limit: 50000B Languages: All except: PERL 6

C语言源程序：

1#include <stdio.h>
2#include <string.h>
3
4#define  L  35000
5int prime[ L ], nprime;
6
7void initPrime() {
8        int i, j;
9        memset( prime, 0sizeof(prime) );
10        nprime = 0;
11        for ( i = 2; i < L; ++i ) {
12                if ( prime[ i ] == 0 ) {
13                        prime[ nprime++ ] = i;
14                        for ( j = i + i; j < L; j += i ) {
15                                prime[ j ] = 1;
16                        }

17                }

18        }

19        prime[ nprime++ ] = L;
20}

21
22int isPrime( int n ) {
23        int i = 0;
24        if ( n == 2 ) {
25                return 1;
26        }

27        while ( (prime[i]*prime[i]<=n) && (n%prime[i]!=0) ) {
28                ++i;
29        }

30        return n % prime[ i ] != 0;
31}

32
33int main() {
34        int td, a, b;
35        initPrime();
36        scanf( "%d"&td );
37        while ( td-- > 0 ) {
38                scanf( "%d%d"&a, &b );
39                if ( a < 2 ) {
40                        a = 2;
41                }

42                while ( a <= b ) {
43                        if ( isPrime( a ) ) {
44                                printf( "%d\n", a );
45                        }

46                        ++a;
47                }

48                if ( td > 0 ) {
49                        printf( "\n" );
50                }

51        }

52        return 0;
53}

54

1; SPOJ 2
2
3section  .bss
4        prime : resd 35000
5        nPrime : resd 1
6        outBuf : resb 20000000
7        nOutBuf : resd 1
8
9section .text
10        global _start
11
12_start :
13        mov eax, outBuf
14        mov [nOutBuf], eax
15        call initPrime
16        call inInt
17        push eax
18CASE :
19        call inInt
20        dec eax
21        push eax
22        call inInt
23        mov ebx, eax
24        pop eax
25        push ebx
26        push eax
27LOOP :
28        mov eax, [esp]
29        inc eax
30        mov [esp], eax
31        call isPrime
32        test ecx, ecx
33        jz SKIP
34        mov eax, [esp]
35        call outInt
36        call outLn
37SKIP :
38        mov eax, [esp]
39        mov ebx, [esp+4]
40        cmp eax, ebx
41        jne LOOP
42        pop eax
43        pop ebx
44        pop eax
45        dec eax
46        test eax, eax
47        jz EXIT
48        push eax
49        call outLn
50        jmp CASE
51EXIT :
52        call flushOutBuf
53        mov eax, 1
54        mov ebx, 0
55        int 0x80
56
57; eax = inInt
58inInt :
59        sub esp, 8
60        xor eax, eax
61        mov [esp], eax
62    L1 :
63        mov eax, 3
64        mov ebx, 0
65        mov ecx, esp
67        mov edx, 1
68        int 0x80
69        xor eax, eax
70        mov al, byte [ecx]
71        cmp al, '0'
72        jb  L2
73        cmp al, '9'
74        ja L2
75        mov ebx, eax
76        sub ebx, '0'
77        mov ecx, 10
78        mov eax, [esp]
79        xor edx, edx
80        mul ecx
82        mov [esp], eax
83        jmp L1
84    L2 :
85        mov eax, [esp]
86        test eax, eax
87        jz L1
89        ret
90
91out eax
92outInt :
93        mov ecx, esp
94        mov ebx, esp
95        sub esp, 64
96        push ecx
97        mov ecx, 10
98    L3 :
99        test eax, eax
100        jz L4
101        xor edx, edx
102        div ecx
104        dec ebx
105        mov byte[ebx], dl
106        jmp L3
107    L4 :
108        mov eax, [nOutBuf]
109        pop edx
110    OIB :
111        cmp ebx, edx
112        jnb OIE
113        cmp eax, nOutBuf
114        jb OISF
115        mov [nOutBuf], eax
116        push ebx
117        push edx
118        call flushOutBuf
119        pop edx
120        pop ebx
121        mov eax, [nOutBuf]
122    OISF :
123        mov cl, byte[ebx]
124        mov byte[eax], cl
125        inc eax
126        inc ebx
127        jmp OIB
128    OIE :
129        mov [nOutBuf], eax
131        ret
132
133outLn :
134        mov eax, [nOutBuf]
135        cmp eax, nOutBuf
136        jb OLE
137        call flushOutBuf
138    OLE :
139        mov eax, [nOutBuf]
140        mov byte [eax], 0xA
141        inc eax
142        mov [nOutBuf], eax
143        ret
144
145initPrime :
146        mov eax, prime
147    IB :
148        cmp eax, nPrime
149        jnb IE
150        mov dword[eax], 0
152        jmp IB
153    IE :
154        mov eax, prime
155        mov ebx, eax
157    SB :
158        cmp eax, nPrime
159        jnb SE
160        mov ecx, [eax]
162        test ecx, ecx
163        jnz SB
164        mov ecx, eax
165        sub ecx, 4
166        sub ecx, prime
167        shr ecx, 2
168        mov [ebx], ecx
170        mov edx, eax
171        sub edx, 4
172        mov ecx, edx
173        sub edx, prime
175    SM :
176        cmp ecx, nPrime
177        jnb SB
178        mov dword [ecx], 1
180        jmp SM
181    SE :
182        mov [nPrime], ebx
183        ret
184
185; ecx = isPrime( eax )
186isPrime :
187        push eax
188        cmp eax, 2
189        jb IPN
190        mov ebx, prime
191    IPB :
192        cmp ebx, [nPrime]
193        jnb IPI
194        mov eax, [ebx]
195        mov ecx, eax
196        xor edx, edx
197        mul ecx
198        mov edx, [esp]
199        cmp eax, edx
200        ja IPI
201        mov eax, edx
203        xor edx, edx
204        div ecx
205        test edx, edx
206        jnz IPB
207    IPN :
208        xor ecx, ecx
209        jmp IPE
210    IPI :
211        mov ecx, 1
212    IPE :
213        pop eax
214        ret
215
216; flush out buffer
217flushOutBuf :
218        mov eax, outBuf
219        mov ebx, [nOutBuf]
220        cmp eax, ebx
221        jnb FOBE
222        mov eax, 4
223        mov ebx, 1
224        mov ecx, outBuf
225        mov edx, [nOutBuf]
226        sub edx, outBuf
227        int 0x80
228        mov eax, outBuf
229        mov [nOutBuf], eax
230    FOBE :
231        ret
232
233

posted on 2011-04-01 18:45 coreBugZJ 阅读(1537) 评论(3)  编辑 收藏 引用 所属分类: Assemble

### Feedback

#### #re: SPOJ 2，Prime Generator 2011-04-01 20:01 ktprime

segment cache size = 62 k : 1929600
PI(1000000000) = 50847534, time use 267.13 ms

[command or number] : e12 e9
segment cache size = 511 k : 15724800
init SegOffset time use 2 ms, cache size = 511 k
PI[1000000000000, 1001000000000] = 36190991, time use 849.76 ms

[command or number] : e16 e9
init SegOffset time use 167 ms, cache size = 511 k
PI[10000000000000000, 10000001000000000] = 27153205, time use 2544.52 ms
回复  更多评论

@ktprime