assembly 检查8086组件中的素数

aemubtdh  于 2023-05-23  发布在  其他
关注(0)|答案(1)|浏览(190)

我试图检查如果一个给定的数字是素数或不是在8086汇编程序使用涡轮汇编。但是也许我的代码中有什么错误，对于一些素数（19，23，31，37），它显示它不是素数。其余的质数（2，3，5，7，11，17，29，41，...，71）运行良好。
下面是整个代码：

DATA SEGMENT
NUM DB 37H
PR DB 0H
NPR DB 0H
DATA ENDS

CODE SEGMENT
START: ASSUME CS:CODE, DS:DATA
MOV AX, DATA
MOV DS, AX
MOV AL, NUM
MOV BL, 02H
MOV BH,00H
MOV DX,0000H
MOV AH,00H

UP:DIV BL 
CMP AH,00H
JNE NEXT
INC BH
NEXT: CMP BH, 02H
JE NPRIME
INC BL
MOV AX, 0000H
MOV DX, 0000H
MOV AL, NUM
CMP BL, NUM
JBE UP

PRIME: 
INC PR
JMP EXIT

NPRIME: 
INC NPR

EXIT:
MOV AH, 4CH
INT 21H

CODE ENDS
END START

也许问题就出在这一部分？

UP:DIV BL 
CMP AH,00H
JNE NEXT
INC BH
NEXT: CMP BH, 02H
JE NPRIME
INC BL
MOV AX, 0000H
MOV DX, 0000H
MOV AL, NUM
CMP BL, NUM
JBE UP

请让我知道我错在哪里，提前感谢！

assembly

1条答案

按热度按时间
4urapxun

4urapxun1#

我试过你的程序，它工作正常，除了你似乎认为0和1素数。不对
质数是一个大于1的数，它只能被它自己和1整除。
快速修复方法如下：

...
MOV AL, NUM
cmp al, 2           <<<< Add this line
jb  NPRIME          <<<< Add this line
MOV BL, 02H
MOV BH,00H
MOV DX,0000H
MOV AH,00H

UP:DIV BL 
CMP AH,00H
JNE NEXT
INC BH
NEXT: CMP BH, 02H
JE NPRIME
INC BL
MOV AX, 0000H
MOV DX, 0000H
MOV AL, NUM
CMP BL, NUM
JBE UP

PRIME: 
INC PR
JMP EXIT

NPRIME: 
INC NPR

EXIT:
...

如果我就这么说的话，那就不算什么答案了！因此，请允许我发表以下看法：

  • DX归零是重复两次的冗余操作
  • 您可以在一次操作中加载BH和BL
  • 不要在两个不同的地方加载数字
  • 变量 PR 和 NPR 是互斥的，因此单个变量就足够了
  • 你不需要分支来增加计数器

更好的解决方案如下：

...
  cmp  NUM, 2
  jb   NPRIME    ; 0 and 1 are no prime numbers
  mov  bx, 0002h ; BH=0 (counter), BL=2 (divisor)
UP:
  mov  al, NUM
  mov  ah, 0
  div  bl
  cmp  ah, 1     ; Only sets carry flag is remainder is 0
  adc  bh, 0     ; Conditional increment of counter
  cmp  bh, 2
  je   NPRIME
  inc  bl
  cmp  bl, NUM
  jbe  UP
PRIME: 
  inc  PR
NPRIME: 
EXIT:
...

因为你的算法会尝试每个除数直到数字本身，所以即使上面提出的修改也不会使程序真正有效。
我可以添加一个至少快10倍的代码版本。如果你感兴趣，请给我留言，也许我可以在周末添加它。
[编辑]

快速查素

尝试减少迭代次数，特别是除法的次数（div是一个代价高昂的操作）是我们在这里所追求的：

  • 最有效的方法是先把小的数[0，3]分开。这避免了循环中的额外测试。
  • 接下来我们把偶数分开，因为除了2（我们已经分开了），没有偶数是质数。
  • 因此，循环只需要划分奇数。我们可以一次省略所有的偶数约数，因为奇数除以偶数永远不会产生零余数。
  • 我们只需要测试除数的整数平方根。幸运的是，我们不需要计算它。只要除法得到的商仍然大于除数，我们就还没有得到整数的平方根。
; IN (dl) OUT (cx) MOD (ax,bl)
TestPrime:
  xor  cx, cx         ; CX=0 means NotPrime
  cmp  dl, 4
  jb   .Less4
  mov  bl, 1
  test dl, bl
  jz   .No            ; Number is EVEN, so not prime
  ; Remaining candidates {5,7,9,11,13,15,...}
.Loop:
  add  bl, 2          ; Division by {3,5,7,9,11,....}
  mov  al, dl
  mov  ah, 0          ; Will divide AX by BL
  div  bl
  test ah, ah         ; Remainder == 0 ?
  jz   .No            ; Yes, found an additional divisor, so not prime
  cmp  al, bl         ; Quotient > divisor ?
  ja   .Loop          ; Yes, continue up to isqrt(number)
.Yes:
  inc  cx             ; CX=1 means Prime
  ret
.Less4:
  cmp  dl, 2
  jae  .Yes           ; 2 and 3 are prime, 0 and 1 are not prime
.No:
  ret

小于256的素数

下表显示了执行的DIV指令的数量以及所用的时间（以纳秒为单位）。中间的列是问题的改进代码，右边的列是今天的优化代码。随着数量的增长，收益也在增长。
| 数量|IsPrime| DIV|国家安全委员会|DIV|国家安全委员会|
| --------------|--------------|--------------|--------------|--------------|--------------|
| 251| 1|二百五十|四一六三|八|四百九十五|
| 二四一|1|二百四十|四一四零|八|四二八|
| 二三九|1|二三八|三九六七|七|二百八十五|
| 二百三十三|1|二三二|三八六九|七|二百六十三|
| 二二九|1|二百二十八|三八零九|七|二百八十五|
| 二百二十七|1|二百二十六|三七七九|七|二百五十五|
| 二百二十三|1|二百二十二|三六九七|七|二百六十三|
| 二一一|1|二百一十|三四九四|七|二百五十五|
| 一百九十九|1|一百九十八|三二九八|七|二百六十三|
| 一百九十七|1|一百九十六|三二七六|七|二百六十三|
| 一百九十三|1|一百九十二|三二九八|七|二百六十三|
| 一百九十一|1|一百九十|三一八六|七|二百六十三|
| 一百八十一|1|一百八十|小行星3020|六|三一五|
| 一百七十九|1|一百七十八|二九九零|六|三百零八|
| 一百七十三|1|一百七十二|两千九百|六|二百八十五|
| 一百六十七|1|一百六十六|2802|六|二三二|
| 一百六十三|1|一百六十二|2742|六|二三二|
| 一百五十七|1|一百五十六|二六六七|六|二百四十|
| 一百五十一|1|一百五十|二六三七|六|二百四十|
| 一百四十九|1|一百四十八|二五二四|六|二百四十|
| 一三九|1|一百三十八|二三八二|六|二百四十|
| 一百三十七|1|一百三十六|二三五二|六|二百四十|
| 一三一|1|一百三十|二二五四|5|二百八十五|
| 一百二十七|1|一百二十六|二一七一|5|二九三|
| 一百一十三|1|一百一十二|一九四六年|5|二百五十五|
| 一百零九|1|一百零八|一八九三年|5|二百二十五|
| 一百零七|1|一百零六|一八七一|5|二百二十五|
| 一百零三|1|一百零二|一八四八|5|二百一十|
| 一百零一|1|一百|一七五零年|5|二百二十五|
| 九十七|1|九十六|一七一三|5|二百二十五|
| 八九|1|八十八|一五五五|四|二百七十|
| 八十三|1|八十二|一四五七|四|二百七十|
| 七十九|1|七十八|一四六五|四|二百四十|
| 七十三|1|七十二|小行星139|四|一百九十五|
| 七十一|1|七十|1284|四|二百零二|
| 六十七|1|六十六|一二零二|四|二百一十|
| 六十一|1|六十|一二零九|四|一百九十五|
| 五十九|1|五十八|一零八二|四|一百九十五|
| 五十三|1|五十二|九七六|3|二百五十五|
| 四十七|1|四十六|八七一|3|二百六十三|
| 四十三|1|四十二|八零四|3|一百八十|
| 四十一|1|四十|七七三|3|一百八十七|
| 三十七|1|三十六|七二八|3|一百七十二|
| 三十一|1|三十|六一六|3|一百八十|
| 二十九|1|二十八|六零一|2|二百二十五|
| 二十三|1|二十二|510| 2|二三二|
| 十九岁|1|十八岁|四三五|2|一百七十二|
| 17个|1|十六岁|四一三|2|一百七十二|
| 十三|1|十二岁|360度|2|一百七十二|
| 十一|1|十个|三一五|1|二一七|
| 七|1|六|二百四十七|1|一百四十二|
| 5| 1|四|二一七|1|一百五十|
| 3| 1| 2|一百八十七|0|一百六十五|
| 2| 1| 1|一百七十二|0|一百六十五|

小于256的非质数

下表显示了执行的DIV指令的数量以及所用的时间（以纳秒为单位）。中间的列是问题的改进代码，右边的列是今天的优化代码。随着数量的增长，收益也在增长。
| 数量|IsPrime| DIV|国家安全委员会|DIV|国家安全委员会|
| --------------|--------------|--------------|--------------|--------------|--------------|
| 二百五十五|0|四|二百七十|1|一百九十五|
| 二百五十四|0|一百二十六|二二六一|0|二百零二|
| 二百五十三|0|二十二|五一八|5|三百四十五|
| 二百五十二|0| 2|二百零二|0|一百八十|
| 二百五十|0|四|二百八十五|0|一百四十二|
| 二四九|0|八十二|一五三二|1|二一七|
| 二百四十八|0| 3|二百四十|0|一百五十|
| 二百四十七|0|十八岁|510|六|三百四十五|
| 二四六|0| 2|二百一十|0|一百六十五|
| 二百四十五|0|六|二百七十|2|二三二|
| 二百四十四|0| 3|二百五十五|0|一百六十五|
| 二百四十三|0|八|三百三十八|1|二一七|
| 二百四十二|0|十个|三百七十五|0|一百八十|
| 二百四十|0| 2|二一七|0|一百五十七|
| 二三八|0|六|360度|0|一百四十二|
| 二三七|0|七十八|一四四二|1|一百八十七|
| 二三六|0| 3|二百四十|0|一百四十二|

| 二百三十五|0|四十六|九一六|2|二三二|
| 二百三十四|0| 2|二百一十|0|一百五十七|
| 二三二|0| 3|一百八十|0|一百五十七|
| 二三一|0|六|二百七十|1|一百八十七|
| 二百三十|0|四|二百四十七|0|一百四十二|
| 二百二十八|0| 2|二百一十|0|一百五十|
| 二百二十六|0|一百一十二|二零六六|0|一百四十二|
| 二百二十五|0|四|二百四十七|1|一百九十五|
| 二百二十四|0| 3|二百四十|0|一百四十二|
| 二百二十二|0| 2|二一七|0|一百五十|
| 二二一|0|十六岁|四三五|六|三百三十八|
| 二百二十|0| 3|二百四十|0|一百五十|
| 二一九|0|七十二|一三五二|1|二百二十五|
| 二一八|0|一百零八|一九三一年|0|一百四十二|
| 二一七|0|三十|六四六|3|二百七十八|
| 二一六|0| 2|二百一十|0|一百五十七|
| 二百一十五|0|四十二|九二四|2|二三二|
| 二一四|0|一百零六|一八九三年|0|一百六十五|
| 二一三|0|七十|一三二|1|二一七|
| 二一二|0| 3|二百四十|0|一百五十七|
| 二百一十|0| 2|一百六十五|0|一百五十|
| 二百零九|0|十八岁|四八八|5|三百二十三|
| 二百零八|0| 3|二百七十|0|一百六十五|
| 二百零七|0|八|二百五十五|1|二一七|
| 二百零六|0|一百零二|一八九三年|0|一百六十五|
| 二百零五|0|四十|八一一|2|二百零二|
| 二百零四|0| 2|二百一十|0|一百六十五|
| 二百零三|0|二十八|六三一|3|二百七十八|
| 二百零二|0|一百|一七九五|0|一百六十五|
| 二百零一|0|六十六|一二五四|1|二一七|
| 两百|0| 3|二百四十|0|一百六十五|
| 一百九十八|0| 2|一百六十五|0|一百五十|
| 一百九十六|0| 3|二三二|0|一百四十二|
| 一百九十五|0|四|二百四十|1|一百八十七|
| 一百九十四|0|九十六|一七五零年|0|一百四十二|
| 一百九十二|0| 2|一百六十五|0|一百五十|
| 一百九十|0|四|三一五|0|一百四十二|
| 一百八十九|0|六|二百七十|1|一百九十五|
| 一百八十八|0| 3|二百五十五|0|一百四十二|
| 一百八十七|0|十六岁|四二八|5|三百零八|
| 一百八十六|0| 2|二百零二|0|一百四十二|
| 一百八十五|0|三十六|八零四|2|二三二|
| 一百八十四|0| 3|二百四十|0|一百六十五|
| 一百八十三|0|六十|一一四二|1|二百二十五|
| 一百八十二|0|六|二百七十|0|一百五十七|
| 一百八十|0| 2|一百六十五|0|一百五十七|
| 一百七十八|0|八十八|一七二零|0|一百四十二|
| 一百七十七|0|五十八|一一三四|1|一百八十七|
| 一百七十六|0| 3|二百四十|0|一百五十|
| 一百七十五|0|六|二百七十|2|二三二|
| 一百七十四|0| 2|二百一十|0|一百八十|
| 一百七十二|0| 3|二百四十|0|一百五十七|
| 一百七十一|0|八|三百|1|一百八十七|
| 一百七十|0|四|二百四十七|0|一百五十|
| 一百六十九|0|一百六十八|二九三八|六|三百四十五|
| 一百六十八|0| 2|二百一十|0|一百六十五|
| 一百六十六|0|八十二|1540| 0|一百四十二|
| 一百六十五|0|四|二百四十|1|二百四十|
| 一百六十四|0| 3|二三二|0|一百五十|
| 一百六十二|0| 2|一百五十七|0|一百五十|
| 一百六十一|0|二十二|510| 3|二百七十八|
| 一百六十|0| 3|二百四十七|0|一百五十七|
| 一百五十九|0|五十二|1014| 1|一百八十七|
| 一百五十八|0|七十八|一四四二|0|一百四十二|
| 一百五十六|0| 2|一百六十五|0|一百四十二|
| 一百五十五|0|三十|六四六|2|二百六十三|
| 一百五十四|0|六|二百七十|0|一百五十|
| 一百五十三|0|八|三百七十五|1|一百八十七|
| 一百五十二|0| 3|二百四十七|0|一百五十七|
| 一百五十|0| 2|二百一十|0|一百五十|
| 一百四十八|0| 3|二百七十|0|一百五十|
| 一百四十七|0|六|二百七十|1|二百零二|
| 一百四十六|0|七十二|一三五二|0|一百五十|
| 一百四十五|0|二十八|六三一|2|二三二|
| 一百四十四|0| 2|二百零二|0|一百五十七|
| 一百四十三|0|十二岁|三百九十|5|三百零八|
| 一百四十二|0|七十|一三七五|0|一百六十五|
| 一百四十一|0|四十六|九一六|1|二百二十五|
| 一百四十|0| 3|二百四十|0|一百六十五|
| 一百三十八|0| 2|一百六十五|0|一百九十五|
| 一百三十六|0| 3|二三二|0|一百五十|
| 一百三十五|0|四|二百四十七|1|一百九十五|
| 一百三十四|0|六十六|一二四七|0|一百四十二|
| 一百三十三|0|十八岁|四八八|3|三百零八|
| 一百三十二|0| 2|一百六十五|0|一百七十二|
| 一百三十|0|四|二百四十七|0|一百八十七|
| 一百二十九|0|四十二|八七九|1|一百九十五|
| 一百二十八|0| 3|二百四十|0|一百六十五|
| 一百二十六|0| 2|一百六十五|0|一百四十二|
| 一百二十五|0|二十四|五五六|2|二百六十三|
| 一百二十四|0| 3|二百四十|0|一百六十五|
| 一百二十三|0|四十|八一一|1|一百五十|
| 一百二十二|0|六十|一二零九|0|一百四十二|
| 一百二十一|0|一百二十|二一三四|5|三百零八|
| 一百二十|0| 2|二百一十|0|一百四十二|
| 一一九|0|十六岁|四七三|3|二百七十八|
| 一百一十八|0|五十八|一一二七|0|一百六十五|
| 一百一十七|0|八|三百|1|二百零二|
| 一百一十六|0| 3|二百四十七|0|一百七十二|
| 一百一十五|0|二十二|五五六|2|二百七十|
| 一百一十四|0| 2|二百一十|0|一百六十五|
| 一百一十二|0| 3|二百四十|0|一百五十|
| 一一一|0|三十六|七五八|1|一百八十七|
| 一百一十|0|四|二百四十|0|一百五十七|
| 一百零八|0| 2|一百六十五|0|一百五十|
| 一百零六|0|五十二|一零九七|0|一百五十|
| 一百零五|0|四|二百四十|1|二百零二|
| 一百零四|0| 3|二百四十|0|一百五十|
| 一百零二|0| 2|一百六十五|0|一百四十二|
| 一百|0| 3|二三二|0|一百五十七|
| 九九|0|八|三百|1|一百六十五|
| 九十八|0|六|二百七十|0|一百六十五|
| 九十六|0| 2|一百六十五|0|一百四十二|
| 九十五|0|十八岁|四八八|2|二一七|
| 九十四|0|四十六|一零三六|0|一百五十|
| 九十三|0|三十|六四六|1|一百九十五|
| 九十二|0| 3|二百四十|0|一百五十七|
| 九十一|0|十二岁|三百九十|3|三百零八|
| 九十|0| 2|二百一十|0|一百八十|
| 八十八|0| 3|二三二|0|一百八十七|
| 八十七|0|二十八|六三一|1|一百八十七|
| 八十六|0|四十二|八七一|0|一百四十二|
| 八十五|0|十六岁|四二八|2|二三二|
| 八十四|0| 2|二百一十|0|一百八十|
| 八十二|0|四十|八一九|0|一百五十七|
| 八十一|0|八|二九三|1|二百零二|
| 八十|0| 3|二三二|0|一百四十二|
| 七十八|0| 2|二百一十|0|一百五十七|
| 七十七|0|十个|三百二十三|3|二百七十八|
| 七十六|0| 3|二三二|0|一百四十二|
| 七十五|0|四|二百四十|1|一百五十|
| 七十四|0|三十六|七五八|0|一百五十|
| 七十二|0| 2|一百六十五|0|一百四十二|
| 七十|0|四|三一五|0|一百四十二|
| 六十九|0|二十二|五一八|1|一百八十七|
| 六十八|0| 3|二百四十|0|一百四十二|
| 六十六|0| 2|一百六十五|0|一百四十二|
| 六十五|0|十二岁|三百九十|2|二三二|
| 六十四|0| 3|二百四十|0|一百四十二|
| 六十三|0|六|二百七十|1|一百五十|
| 六十二|0|三十|六四六|0|一百五十|
| 六十|0| 2|一百六十五|0|一百五十|
| 五十八|0|二十八|七五一|0|一百四十二|
| 五十七|0|十八岁|四八八|1|一百九十五|
| 五十六|0| 3|二百七十|0|一百六十五|
| 五十五|0|十个|三六八|2|二三二|
| 五十四|0| 2|二百零二|0|一百八十|
| 五十二|0| 3|二百四十|0|一百五十七|
| 五十一|0|十六岁|四二八|1|一百九十五|
| 五十|0|四|二百四十|0|一百四十二|
| 四十九|0|四十八|一零四四|3|二百七十|
| 四十八|0| 2|二百一十|0|一百六十五|
| 四十六|0|二十二|五九三|0|一百五十七|
| 四十五|0|四|二百四十|1|一百八十七|
| 四十四|0| 3|二百四十|0|一百六十五|
| 四十二|0| 2|二百零二|0|一百四十二|
| 四十|0| 3|二百七十|0|一百四十二|
| 三十九|0|十二岁|三九八|1|一百八十七|
| 三十八|0|十八岁|四八八|0|一百四十二|

| 三十六|0| 2|二百一十|0|一百五十|
| 三十五|0|六|二百七十|2|二百四十七|
| 34人|0|十六岁|四百二十|0|一百五十|
| 三十三|0|十个|三百二十三|1|一百八十七|
| 三十二|0| 3|二三二|0|一百四十二|
| 三十|0| 2|二百零二|0|一百五十|
| 二十八|0| 3|二百六十三|0|一百六十五|
| 二十七|0|八|二九三|1|一百九十五|
| 二十六|0|十二岁|四六五|0|一百四十二|
| 二十五|0|二十四|五六三|2|二三二|
| 二十四|0| 2|二百一十|0|一百四十二|
| 二十二|0|十个|三百二十三|0|一百五十|
| 二十一|0|六|二百七十|1|二百零二|
| 二十|0| 3|二三二|0|一百五十|
| 十八岁|0| 2|二百二十五|0|一百五十|
| 十六岁|0| 3|二三二|0|一百五十七|
| 十五|0|四|二三二|1|一百八十七|
| 十四岁|0|六|二百六十三|0|一百四十二|
| 十二岁|0| 2|二一七|0|一百五十七|
| 十个|0|四|三一五|0|一百五十七|
| 九|0|八|三百零八|1|二一七|
| 八|0| 3|二百四十七|0|一百五十|
| 六|0| 2|二一七|0|一百四十二|
| 四|0| 3|二百四十|0|一百六十五|
| 1| 0| 0|一百六十五|0|一百八十七|
| 0| 0| 0|一百五十七|0|一百八十七|

赞(0）分享  回复(0）举报  2023-05-23
我来回答

相关问题

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新问答

    更多
    • 蜀ICP备2022004421号-2 NULL123 https://www.null123.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com