Checking Prime number in 8086 Assembly-CodePudding

I am trying to check if a given number is prime or not in 8086 Assembly program using Turbo Assembler. But maybe there is something wrong in my code, for some of the prime numbers(19,23,31,37) its showing its not a prime number. Rest of the prime numbers(2,3,5,7,11,17,29,41,...,71) are working well.

Here's the whole code:

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

Maybe the problem must be in this part?

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

Please let me know where I am going wrong, Thanks in advance!

CodePudding user response：

I have tried your program and it works fine except that you seem to consider 0 and 1 prime numbers. That's not correct.

A prime number is a number bigger than 1, that is only divisible by itself and by 1.

The quick fix is below:

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

Not much of an answer if I would leave it at that! So allow me the following observations:

Zeroing DX is a twice repeated, redundant operation
You can load BH and BL in one operation
Don't load the number at two different places
The variables PR and NPR are mutually exclusive, so a single variable would be enough
You don't need branching in order to increment the counter

The better fix is below:

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

Because your algorithm tries every divisor up to the number itself, even the above proposed changes will not make the program truly efficient.
I could add a version of the code that would be at least 10 times faster. In case you're interested, leave me a comment and perhaps I could add it in the weekend... (along with upvoting your question, something I'm not able to do on this computer here!)