在下面示范一个简单的程式,用一般埃氐筛法(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编辑过]