Checking Prime number in 8086 Assembly

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!

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

[edit]

A fast check for primality

Trying to reduce the number of iterations and especially the number of divisions (div is a costly operation) is what we're after here:

• It is most efficient to split off the small numbers [0,3] first. This avoids extra tests in the loop.
• Next we split off the even numbers because, except for the number 2 (that we already have split off), no even number is prime.
• Therefore the loop only has to divide odd numbers. We can omit all the even divisors at once because dividing an odd number by an even number will never produce a zero remainder.
• We only need to test divisors up to the integer square root of the number. Luckily we don't need to calculate it. As long as the quotient from the division is still greater than the divisor we have not yet reached the integer square root.

; 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

Prime numbers smaller than 256

Next table shows the number of DIV instructions that got executed and the time it took in nanoseconds. The middle columns are for the question's improved code, and the columns on the right are for today's optimized code. As numbers grow, so does the benefit.

Non prime numbers smaller than 256

Next table shows the number of DIV instructions that got executed and the time it took in nanoseconds. The middle columns are for the question's improved code, and the columns on the right are for today's optimized code. As numbers grow, so does the benefit.