Prime or not prime assemble code 8051

Status
Not open for further replies.

Greital

Newbie level 4 hi,
I'm working with a multiple phases project in 8051 micro-controller
and phase one involved with check if a given number is prime or not

the way I've trying to do this code is :
1. assuming 2 numbers one is prime and other is not and save them in R1, and R2
2. create a counter from 99 and save it in R7 --->> 99 because in the following phases we have to check the prime number or not from 1 to 99 (a number that user enter using keypad)
3. making a loop and divide the desire number with 99 first then check if prime or not, then decrements and repeat the loop again until we finish
4. if its prime a led will flash using delay with counter R6=3
5. if its not prime another led will flash using the same delay and same counter

but I'm really stuck with the code, something wrong but I don't now what is ?
any help is appreciable

----->>> I'm using Edsim51D1 to check my code
Code:
----------Begining---------
START:
MOV R1,#9
MOV R2,#31
MOV R7,#99
MOV R6,#3
LOOP:
MOV A,R1
MOV B,R7
DIV AB
MOV R3,#0
MOV R3,B
CJNE R3,#0,NOTPRIME
DJNZ R7,LOOP

PRIME:
ACALL DELAY
CPL P1.3
DJNZ R6,PRIME
AJMP DONE

NOTPRIME:
ACALL DELAY
CPL P1.0
DJNZ R6,NOTPRIME
DONE:

DELAY:
MOV R5,#20
X3:	MOV R4,#200
X2:	MOV R3,#250
X1:	DJNZ R3,X1
DJNZ R4,X2
DJNZ R5,X3
RET

END
-------------End------------

Last edited by a moderator:

Super Moderator
Staff member I thought the standard way of checking for prime is take the number (A) and divide it starting with the divisor of 2 checking for zero remainder. Increment the divisor and check again for zero remainder keep repeating until you reach half of the A value.

If you find a zero remainder the number is not prime.
If you reach a divisor of A/2 and have not found a zero remainder then the number is prime.

Greital

Newbie level 4 thanks for trying to help appreciate it

xenos

Full Member level 4 The remain of the division is checked with factors up to SQRT , not n/2.

An ansient algorithm, like: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
(with a simple modification, you do not have to store anything in memory), could be helpful.

You can see a modern and efficient algorithm here: https://en.wikipedia.org/wiki/Primality_test

Code:
function is_prime(n : integer)
if n ≤ 1
return false
else if n ≤ 3
return true
else if n mod 2 = 0 or n mod 3 = 0
return false
let i ← 5
while i×i ≤ n
if n mod i = 0 or n mod (i + 2) = 0
return false
i ← i + 6
return true

Of course if you need primes up to a relatively small number (eg 256), then you could precalculate the array of primaries and store it in non volatile memory.

Super Moderator
Staff member The remain of the division is checked with factors up to SQRT , not n/2.
Thanks for pointing my error out. I totally forgot that it was supposed to be SQRT and not n/2. The question is though how to determine SQRT for any given n using that 8051? Or are we just going to assume that with the given 8-bit registers used that the maximum is 255 so is automatically <16?

You can see a modern and efficient algorithm here:
Correct me if I'm wrong but it also seems to me that mod isn't necessarily the simplest thing to compute on a 8051 in assembly.

KlausST

Super Moderator
Staff member Hi,

The question is though how to determine SQRT for any given n using that 8051?
Actually square root is difficult...

Usually you test starting from 2. Then the next prime: 3, then 5, then 7... until the result of the devision is smaller than the prime number.

If the numbers to test are values from 0 ..99,
Then the prime numbers used for testing are 2, 3, 5, 7, 11, not more
99 / 7 the result is 14, larger than 7
99/11 the result is 9, smaller than 11...this indicates the end of test
Automatically this is at the square root of 99.

Klaus

• Greital

Greital

Points: 2

xenos

Full Member level 4 The question is though how to determine SQRT for any given n using that 8051?
in stead of calculating sqrt(N), we use:
Code:
if(i*i>N)
break;

Correct me if I'm wrong but it also seems to me that mod isn't necessarily
the simplest thing to compute on a 8051 in assembly.
if time is not critical, we could use a style of dynamic programming algorithm:
Code:
//check if N is divided by K
TMP = 0;
for(i=1;TMP<=N;i++)
TMP += K;
if(TMP == K)
the number is divided completely by K (N %K == 0)
i.e. without any multiplication or division or modulo, we check if a modulo is zero.
We should take extra care to check STATUS flags, if overflow in addition occur, then TMP got larger than N and we should terminate the loop.

Greital

Newbie level 4 thanks to all of you you all helped me to configure the ideas to do this code 