Search code examples
assemblyprimesx86-16tasm

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!

Solution

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

    Number IsPrime DIV's nsec DIV's nsec
    251 1 250 4163 8 495
    241 1 240 4140 8 428
    239 1 238 3967 7 285
    233 1 232 3869 7 263
    229 1 228 3809 7 285
    227 1 226 3779 7 255
    223 1 222 3697 7 263
    211 1 210 3494 7 255
    199 1 198 3298 7 263
    197 1 196 3276 7 263
    193 1 192 3298 7 263
    191 1 190 3186 7 263
    181 1 180 3020 6 315
    179 1 178 2990 6 308
    173 1 172 2900 6 285
    167 1 166 2802 6 232
    163 1 162 2742 6 232
    157 1 156 2667 6 240
    151 1 150 2637 6 240
    149 1 148 2524 6 240
    139 1 138 2382 6 240
    137 1 136 2352 6 240
    131 1 130 2254 5 285
    127 1 126 2171 5 293
    113 1 112 1946 5 255
    109 1 108 1893 5 225
    107 1 106 1871 5 225
    103 1 102 1848 5 210
    101 1 100 1750 5 225
    97 1 96 1713 5 225
    89 1 88 1555 4 270
    83 1 82 1457 4 270
    79 1 78 1465 4 240
    73 1 72 1390 4 195
    71 1 70 1284 4 202
    67 1 66 1202 4 210
    61 1 60 1209 4 195
    59 1 58 1082 4 195
    53 1 52 976 3 255
    47 1 46 871 3 263
    43 1 42 804 3 180
    41 1 40 773 3 187
    37 1 36 728 3 172
    31 1 30 616 3 180
    29 1 28 601 2 225
    23 1 22 510 2 232
    19 1 18 435 2 172
    17 1 16 413 2 172
    13 1 12 360 2 172
    11 1 10 315 1 217
    7 1 6 247 1 142
    5 1 4 217 1 150
    3 1 2 187 0 165
    2 1 1 172 0 165

    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.

    Number IsPrime DIV's nsec DIV's nsec
    255 0 4 270 1 195
    254 0 126 2261 0 202
    253 0 22 518 5 345
    252 0 2 202 0 180
    250 0 4 285 0 142
    249 0 82 1532 1 217
    248 0 3 240 0 150
    247 0 18 510 6 345
    246 0 2 210 0 165
    245 0 6 270 2 232
    244 0 3 255 0 165
    243 0 8 338 1 217
    242 0 10 375 0 180
    240 0 2 217 0 157
    238 0 6 360 0 142
    237 0 78 1442 1 187
    236 0 3 240 0 142
    235 0 46 916 2 232
    234 0 2 210 0 157
    232 0 3 180 0 157
    231 0 6 270 1 187
    230 0 4 247 0 142
    228 0 2 210 0 150
    226 0 112 2066 0 142
    225 0 4 247 1 195
    224 0 3 240 0 142
    222 0 2 217 0 150
    221 0 16 435 6 338
    220 0 3 240 0 150
    219 0 72 1352 1 225
    218 0 108 1931 0 142
    217 0 30 646 3 278
    216 0 2 210 0 157
    215 0 42 924 2 232
    214 0 106 1893 0 165
    213 0 70 1322 1 217
    212 0 3 240 0 157
    210 0 2 165 0 150
    209 0 18 488 5 323
    208 0 3 270 0 165
    207 0 8 255 1 217
    206 0 102 1893 0 165
    205 0 40 811 2 202
    204 0 2 210 0 165
    203 0 28 631 3 278
    202 0 100 1795 0 165
    201 0 66 1254 1 217
    200 0 3 240 0 165
    198 0 2 165 0 150
    196 0 3 232 0 142
    195 0 4 240 1 187
    194 0 96 1750 0 142
    192 0 2 165 0 150
    190 0 4 315 0 142
    189 0 6 270 1 195
    188 0 3 255 0 142
    187 0 16 428 5 308
    186 0 2 202 0 142
    185 0 36 804 2 232
    184 0 3 240 0 165
    183 0 60 1142 1 225
    182 0 6 270 0 157
    180 0 2 165 0 157
    178 0 88 1720 0 142
    177 0 58 1134 1 187
    176 0 3 240 0 150
    175 0 6 270 2 232
    174 0 2 210 0 180
    172 0 3 240 0 157
    171 0 8 300 1 187
    170 0 4 247 0 150
    169 0 168 2938 6 345
    168 0 2 210 0 165
    166 0 82 1540 0 142
    165 0 4 240 1 240
    164 0 3 232 0 150
    162 0 2 157 0 150
    161 0 22 510 3 278
    160 0 3 247 0 157
    159 0 52 1014 1 187
    158 0 78 1442 0 142
    156 0 2 165 0 142
    155 0 30 646 2 263
    154 0 6 270 0 150
    153 0 8 375 1 187
    152 0 3 247 0 157
    150 0 2 210 0 150
    148 0 3 270 0 150
    147 0 6 270 1 202
    146 0 72 1352 0 150
    145 0 28 631 2 232
    144 0 2 202 0 157
    143 0 12 390 5 308
    142 0 70 1375 0 165
    141 0 46 916 1 225
    140 0 3 240 0 165
    138 0 2 165 0 195
    136 0 3 232 0 150
    135 0 4 247 1 195
    134 0 66 1247 0 142
    133 0 18 488 3 308
    132 0 2 165 0 172
    130 0 4 247 0 187
    129 0 42 879 1 195
    128 0 3 240 0 165
    126 0 2 165 0 142
    125 0 24 556 2 263
    124 0 3 240 0 165
    123 0 40 811 1 150
    122 0 60 1209 0 142
    121 0 120 2134 5 308
    120 0 2 210 0 142
    119 0 16 473 3 278
    118 0 58 1127 0 165
    117 0 8 300 1 202
    116 0 3 247 0 172
    115 0 22 556 2 270
    114 0 2 210 0 165
    112 0 3 240 0 150
    111 0 36 758 1 187
    110 0 4 240 0 157
    108 0 2 165 0 150
    106 0 52 1097 0 150
    105 0 4 240 1 202
    104 0 3 240 0 150
    102 0 2 165 0 142
    100 0 3 232 0 157
    99 0 8 300 1 165
    98 0 6 270 0 165
    96 0 2 165 0 142
    95 0 18 488 2 217
    94 0 46 1036 0 150
    93 0 30 646 1 195
    92 0 3 240 0 157
    91 0 12 390 3 308
    90 0 2 210 0 180
    88 0 3 232 0 187
    87 0 28 631 1 187
    86 0 42 871 0 142
    85 0 16 428 2 232
    84 0 2 210 0 180
    82 0 40 819 0 157
    81 0 8 293 1 202
    80 0 3 232 0 142
    78 0 2 210 0 157
    77 0 10 323 3 278
    76 0 3 232 0 142
    75 0 4 240 1 150
    74 0 36 758 0 150
    72 0 2 165 0 142
    70 0 4 315 0 142
    69 0 22 518 1 187
    68 0 3 240 0 142
    66 0 2 165 0 142
    65 0 12 390 2 232
    64 0 3 240 0 142
    63 0 6 270 1 150
    62 0 30 646 0 150
    60 0 2 165 0 150
    58 0 28 751 0 142
    57 0 18 488 1 195
    56 0 3 270 0 165
    55 0 10 368 2 232
    54 0 2 202 0 180
    52 0 3 240 0 157
    51 0 16 428 1 195
    50 0 4 240 0 142
    49 0 48 1044 3 270
    48 0 2 210 0 165
    46 0 22 593 0 157
    45 0 4 240 1 187
    44 0 3 240 0 165
    42 0 2 202 0 142
    40 0 3 270 0 142
    39 0 12 398 1 187
    38 0 18 488 0 142
    36 0 2 210 0 150
    35 0 6 270 2 247
    34 0 16 420 0 150
    33 0 10 323 1 187
    32 0 3 232 0 142
    30 0 2 202 0 150
    28 0 3 263 0 165
    27 0 8 293 1 195
    26 0 12 465 0 142
    25 0 24 563 2 232
    24 0 2 210 0 142
    22 0 10 323 0 150
    21 0 6 270 1 202
    20 0 3 232 0 150
    18 0 2 225 0 150
    16 0 3 232 0 157
    15 0 4 232 1 187
    14 0 6 263 0 142
    12 0 2 217 0 157
    10 0 4 315 0 157
    9 0 8 308 1 217
    8 0 3 247 0 150
    6 0 2 217 0 142
    4 0 3 240 0 165
    1 0 0 165 0 187
    0 0 0 157 0 187