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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
4
#define L 35000
5
int prime[ L ], nprime;
6![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
7![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void initPrime()
{
8
int i, j;
9
memset( prime, 0, sizeof(prime) );
10
nprime = 0;
11![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for ( i = 2; i < L; ++i )
{
12![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if ( prime[ i ] == 0 )
{
13
prime[ nprime++ ] = i;
14![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for ( j = i + i; j < L; j += i )
{
15
prime[ j ] = 1;
16
}
17
}
18
}
19
prime[ nprime++ ] = L;
20
}
21![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
22![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int isPrime( int n )
{
23
int i = 0;
24![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if ( n == 2 )
{
25
return 1;
26
}
27![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while ( (prime[i]*prime[i]<=n) && (n%prime[i]!=0) )
{
28
++i;
29
}
30
return n % prime[ i ] != 0;
31
}
32![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
33![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
34
int td, a, b;
35
initPrime();
36
scanf( "%d", &td );
37![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while ( td-- > 0 )
{
38
scanf( "%d%d", &a, &b );
39![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if ( a < 2 )
{
40
a = 2;
41
}
42![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while ( a <= b )
{
43![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if ( isPrime( a ) )
{
44
printf( "%d\n", a );
45
}
46
++a;
47
}
48![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if ( td > 0 )
{
49
printf( "\n" );
50
}
51
}
52
return 0;
53
}
54![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
汇编源程序:
1
; SPOJ 2
2![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
3
section .bss
4
prime : resd 35000
5
nPrime : resd 1
6
outBuf : resb 20000000
7
nOutBuf : resd 1
8![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
9
section .text
10
global _start
11![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
12
_start :
13
mov eax, outBuf
14
mov [nOutBuf], eax
15
call initPrime
16
call inInt
17
push eax
18
CASE :
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
27
LOOP :
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
37
SKIP :
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
51
EXIT :
52
call flushOutBuf
53
mov eax, 1
54
mov ebx, 0
55
int 0x80
56![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
57
; eax = inInt
58
inInt :
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
91
; out eax
92
outInt :
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
133
outLn :
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
145
initPrime :
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
185
; ecx = isPrime( eax )
186
isPrime :
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
216
; flush out buffer
217
flushOutBuf :
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
233![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)