SPOJ Problem Set (classical)
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 |
分析：就是判斷質數，預先開一個 35000 （其平方大于 n 的最大值）內的質數表。。。
C語言源程序：
1
#include <stdio.h>
2#include <string.h>
3
4#define L 35000
5int prime[ L ], nprime;
6
7
void initPrime() 
{
8
int i, j;
9 memset( prime, 0, sizeof(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
66 add ecx, 4
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
81 add eax, ebx
82 mov [esp], eax
83 jmp L1
84 L2 :
85 mov eax, [esp]
86 test eax, eax
87 jz L1
88 add esp, 8
89 ret
90
91; out 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
103 add edx, '0'
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
130 add esp, 64
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
151 add eax, 4
152 jmp IB
153 IE :
154 mov eax, prime
155 mov ebx, eax
156 add eax, 8
157 SB :
158 cmp eax, nPrime
159 jnb SE
160 mov ecx, [eax]
161 add eax, 4
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
169 add ebx, 4
170 mov edx, eax
171 sub edx, 4
172 mov ecx, edx
173 sub edx, prime
174 add ecx, edx
175 SM :
176 cmp ecx, nPrime
177 jnb SB
178 mov dword [ecx], 1
179 add ecx, edx
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
202 add ebx, 4
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