如何显示1-100000的质数?
在一个论坛里有人问如何显示1-100000的质数?在下面示范一个简单的程式,用一般埃氐筛法(sieve of Eratosthenes),原理是从2开始,将每个质数的各个倍数,标记成合数,最后没有标记的就是质数。
题目要求100000内,所以用了两个64k内存作为筛选表。
程序代码:
sqt equ 317 ;100000的平方根 max equ 100000 ;范围 ;----------------------------------------------------- stack segment db 1024 dup (0) ;栈 stack ends data segment seg1 db 65535 dup(0),0 ;第一资料段64k,0-65535 data ends data1 segment seg2 db 65535 dup(0),0 ;第二资料段64k,0-65535 data1 ends ;----------------------------------------------------- code segment assume cs:code,ds:data,ss:stack start: cli ;关闭中断以设定栈 mov ax,stack ;取段值 mov ss,ax mov sp,1024 ;栈顶 sti ;开启中断 next10: mov ax,1 ;1=标示合数 mov si,ax ;si=0001起始值 next20: mov dx,data ;取段值 mov ds,dx inc si ;下一个 cmp si,sqt ;是否到了最大数的平方根 ja next50 ;已到 cmp [si],al ;是否1,是则已标示为合数 jz next20 ;是,回去 next30: mov bx,si ;存该值 mov bp,si ;存该值 add bx,bx ;叠加 mov dx,data ;取第1段值 mov ds,dx mov cx,2 ;2个段 next40: mov [bx],al ;设定该地址为合数 add bx,bp ;再叠加 jnc next40 ;是否超过一段64k,未超过再叠加 mov dx,data1 ;已超过一段64k,取下一64k段 mov ds,dx ;置值 loop next40 ;2个段 jmp short next20 ;下一个 .386 ;386指令可用 ;到此已在二个64k段中标示出所有合数(=1),质数(=0) next50: mov esi,2 ;起始值,范围0-100000,须用32暂存器 mov ebp,max-1 ;最大值 mov dx,data ;取段值 mov ds,dx next60: cmp byte ptr [si],0 ;是否质数 jnz next70 ;若是合数(不是0)则跳 mov eax,esi ;取值 call print_EAX ;印出 mov dl,20h ;空白 mov ah,2 ;印出空白 int 21h next70: inc si ;下一个 jnz next80 ;若不是0,则仍在第1段,跳 mov esi,65536 ;若SI=0,已超过第1段64K,手动令SI=00010000H mov dx,data1 ;取下一段值 mov ds,dx next80: dec ebp ;倒数 jnz next60 ;未到0,再来 mov ah,4ch ;返回dos int 21h ;-------------- 输出eax(32bit)值子程序 ---------------------- Print_EAX: pushad ;保存全部暂存器 mov ecx,0 ;清0 mov ebp,10 ;除法准备 Pax1: mov edx,0 ;清0 div ebp ;ax /10 ,若1234 ,除10后,dl得余数4, push edx ;保存, ax=1234,依次保存4,3,2,1 inc ecx ;累加个数 or eax,eax ;是否已除尽 jnz Pax1 ;不是,再除 Pax2: pop edx ;后入先出,先印出第一数,然后第二... or dl,30h ;转ascii mov ah,2 ;印出 int 21h loop Pax2 ;下一个 popad ;取回全部暂存器 ret ;返回父程序 ;----------------------------------------------------- code ends END start ;程式结束
以下是输出结果
[此贴子已经被作者于2019-11-15 20:56编辑过]