3 Replies - 1806 Views - Last Post: 26 February 2009 - 01:13 PM Rate Topic: -----

#1 goutamteja  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 25-January 09

checki whether a number is prime or not

Post icon  Posted 25 January 2009 - 04:06 AM

hi everyone. I wrote a program to check whether a number is prime or not.
While executing using TASM i am not getting the desired output.
To be more specific, I used the statement "div cx" to divide the no. and see if there is any remainder and its giving the expected result only sometimes.can anyone pls tell me where the problem is???
data segment
org 0600h
prime1 db ?
count1 db 0
data ends
code segment
assume cs:code,ds:data
start:
	mov si,0500h
	mov bl,[si]
	mov cx,2
	call prime
	pop cx
	pop bx
	hlt
prime proc near
	push cx
	push bx

l:	mov ax,bx
	div cx
	cmp dx,0
	je count
	inc cx
	cmp cx,bx
	jle l
count:	inc count1
	cmp cx,bx
	je pr
	inc cx
	cmp count1,1
	jg exit
	jmp l
pr:	mov prime1,1
	jmp exit
exit:	ret
	endp
	code ends
	end start
	


Is This A Good Question/Topic? 0
  • +

Replies To: checki whether a number is prime or not

#2 ayman_mastermind  Icon User is offline

  • human.setType("geek");
  • member icon

Reputation: 126
  • View blog
  • Posts: 1,860
  • Joined: 12-December 08

Re: checki whether a number is prime or not

Posted 25 January 2009 - 05:25 AM

Actually i did a similar exercise but in java some time ago, what my algorith was like is to check wether there is a remainder, for every remainder that appears i increment a variable i call counter, if that variable counter had a value greater than 2 then it is not a prime number as this means that it is divisible by more than 1 and itself, and if the counter ended up being equal to two then definitely the number should be a prime. The program should divide the chosen number(by the user) with the numbers from 1 to the number chosen by itself and the program should count how many times there was a remainder, since the program starts checking from 1 to the number chosen, if the counted remainders are only 2 then it is prime, if the counted remainders are more than two then it is not prime... I hope i was clear enough, anyways good luck in your program and i hope this helps ;)
Was This Post Helpful? 0
  • +
  • -

#3 goutamteja  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 25-January 09

Re: checki whether a number is prime or not

Posted 25 January 2009 - 05:53 AM

View Postayman_mastermind, on 25 Jan, 2009 - 04:25 AM, said:

Actually i did a similar exercise but in java some time ago, what my algorith was like is to check wether there is a remainder, for every remainder that appears i increment a variable i call counter, if that variable counter had a value greater than 2 then it is not a prime number as this means that it is divisible by more than 1 and itself, and if the counter ended up being equal to two then definitely the number should be a prime. The program should divide the chosen number(by the user) with the numbers from 1 to the number chosen by itself and the program should count how many times there was a remainder, since the program starts checking from 1 to the number chosen, if the counted remainders are only 2 then it is prime, if the counted remainders are more than two then it is not prime... I hope i was clear enough, anyways good luck in your program and i hope this helps ;)

i understood what u said and I did it the same way,which u'll understand if u look at the code i posted. But when i am executing it i am not getting the expected result. For example,when i gave the input as 7 and started executing it line by line, i got remainder as 2(DX=2) when divided by 4 and later got remainder as 2 again when divided by 7, when it was supposed to be 0.
So i request you to execute the code i posted and help me sort this out.
Was This Post Helpful? 0
  • +
  • -

#4 astradyne  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 25-February 09

Re: checki whether a number is prime or not

Posted 26 February 2009 - 01:13 PM

Hi

It's been a long long time since I did any 8086 assembler coding - roughly 15-20 years - so hopefully my mind isn't playing tricks on me.

Initial thoughts are that the code should do what you're expecting - I can't see anything glaringly obvious - although you could streamline the code a little to make it more efficient:

	data segment
	org 0600h
	prime1 db ?
	count1 db 0
	data ends
	code segment
	assume cs:code,ds:data

start:	mov si,0500h
		mov bl,[si]
		mov cx,2
		call prime
		pop cx
		pop bx
		hlt

	prime proc near

	push cx
	push bx

loop:	mov ax,bx
	div cx
	cmp dx,0
	je check
	inc cx
	jmp loop

check:	mov prime1,1
	cmp cx,bx
	je exit
	mov prime1,0

exit:	ret
	
	endp
	code ends
	end start



In your code you're starting your check at 2 and checking every increment up to and inluding the number passed. This works, but you only really need to know to check up to the first divisor that leaves no remainder in the DX register. For the number to be prime the divisor mut equal the number you're checking - anything else means the number isn't prime.

In the code above I'm not checking whether CX is the same as BX after the increment because the DIV CX and JE CHECK does that for me and saves a couple of instructions too.

One assumption I do make in the above is that the number being checked is 2 or more. Ideally there should be some sort of validation, but I leave that for others to add as they see fit.

Finally, the above can be made even more efficient by halving the range of numbers being checked as anything greater than half the number cannot be divided completely into the number being checked. For example, if you were checking the number 7, you only need to divide by 2 and 3 as they are less than 3.5. The values 4, 5 and 6 couldn't possibly divide wholly into 7 as they are more than half.

This may not make any difference for small numbers, but if you were to test 1,978,436,527 you would see an improvement in speed.

Anyway, good luck and I hope it helps. If I've made a mistake in the above I plead senility :)

ALl the best

Jonathan
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1