coreBugZJ

此 blog 已弃。

SPOJ 2,Prime Generator

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
 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
 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
 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
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

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

Feedback

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

计算区间太小不能显示筛法的威力
我的程序计算长度为10^9也不到一秒
segment cache size = 62 k : 1929600
thread 1 is finished
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
  回复  更多评论   

# re: SPOJ 2,Prime Generator 2011-04-04 08:34 coreBugZJ

@ktprime
表示仰慕!这个题目数据规模小,就简单化处理了  回复  更多评论   



只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理