# prime numbers using array

i have an assignment that has two steps. the first step is to use an array of cups. then up to the max number of cups (500), i am to step through the array (at multiples of the current array index) and xor the cups - so i'm basically flipping between one and zero each time the cup is hit at multiples of 1, then multiples of 2, then multiples of 3... etc. at the end of it, there is a pattern of numbers (in this case, that pattern is the squares of each number from 1-15: 1, 4, 9, 16, 25, etc.). that program is found below. the second part is to get prime numbers. there is something about the process of flipping back and forth between the one and zero that produces that pattern. once we know that pattern, we should be able to figure out the couple lines of code to chage to produce the prime numbers.

i've been spinning on this for weeks now and i can't see the cause of the pattern. it is probably staring me in the face... can someone be a pair of fresh eyes on my code and give me a clue as to how to alter it to produce prime numbers?

thanks!!

INCLUDE PCMAC.INC
.MODEL SMALL
.586

.STACK 100h

.DATA
CR EQU 13
LF EQU 10
Header DB 'Begin', cr, lf, '\$'
Cup DB 500 DUP (0) ;sets up an array of 500 filled elements
num DW 500 ;to store the number in the array
index DW ? ;start at index=1 to go through each element in the array
step DW ? ;for the inner loop to step through the num array at intervals of index
new DB CR, LF, '\$'
space DB ' - \$'

.CODE
EXTRN GetDDec : NEAR, PutDDec : NEAR, GetDec : NEAR, PutDec : NEAR
ERAT PROC
_Begin

;using index to represent the true nth number starting at 1 (not 0)
mov index, 0 ;start the sieve with the number 1 (ignore 0)

oloop:
inc index ;increment index when outer loop is entered (1->500)
mov ax, 0
mov ax, num
inc ax ;so that it's one more than the array to get to the last number
.IF index < ax
mov ax, 0 ;make y=index every time outer loop is entered
mov ax, index
mov step, ax ;set step = index in the outer loop to get it ready for inner loop
.ELSE
mov ax, 1 ;reset index for the print loop
mov index, ax
jmp ploop
.ENDIF

iloop:
mov ax, 0
mov bx, 0
mov cx, 0
mov bx, step ;bx now contains the current step of the index
mov ax, 0
mov ax, num
inc ax ;so that it's one more than the array to get to the last number
.IF bx < ax ;inner loop checks the current step then goes by step through the array
mov ax, 0
mov cx, 0
mov dx, 0
xor [Cup+bx], 1
mov cl, [Cup+bx] ;for codeview to check the value

.ELSE
jmp oloop

.ENDIF

mov ax, 0
mov ax, index
jmp iloop

ploop:
mov ax, 0
mov ax, num
inc ax ;so that it's one more than the array to get to the last number

.IF index < ax
mov ax, 0
mov bx, 0
mov dx, 0
mov bx, index ;printing starts with 1
mov dl, [Cup + bx]
.IF dl == 1
mov ax, index
call PutDec
sPutStr space
inc index
jmp ploop
.ELSE
inc index
jmp ploop
.ENDIF
.ENDIF

endprgm:

_Exit 0
ERAT ENDP

END ERAT ; Tells where to start execution

• One thing in your code is that you move a value to a reg,
then move another value to the same reg.
That makes the first move, wasted code.
Your code has so much of that going on, that it may be the cause of some confusion as to what the code is actually doing. Example:

MOV AX,5 ;this should be removed
MOV AX,7

• definitely something to consider... i've just been through so many iterations of this thing trying to get to the bottom of it... i'll clean it up a bit and take another looksee... thanks

: One thing in your code is that you move a value to a reg,
: then move another value to the same reg.
: That makes the first move, wasted code.
: Your code has so much of that going on, that it may be the cause of some confusion as to what the code is actually doing. Example:
:
: MOV AX,5 ;this should be removed
: MOV AX,7
:
:
:

• [b][red]This message was edited by peret at 2003-12-3 18:42:49[/red][/b][hr]
[b][red]This message was edited by peret at 2003-12-3 18:29:55[/red][/b][hr]
: definitely something to consider... i've just been through so many iterations of this thing trying to get to the bottom of it... i'll clean it up a bit and take another looksee... thanks

What you're trying to run is the Sieve of Eratosthenes. Here's a good exposition:

http://books.nap.edu/books/0309085497/html/100.html#pagetop

Actually, from looking at your code I can't see how you can ever have a number other than 1 or 0 in any cup. "xor [cup+bx],1" is the only place you ever change the value, and the result can only be 1 or 0.

• : Actually, from looking at your code I can't see how you can ever have a number other than 1 or 0 in any cup. "xor [cup+bx],1" is the only place you ever change the value, and the result can only be 1 or 0.

Yep, that's the problem. You don't want to XOR with 1. You want to XOR with whatever's in BX. Since that can go to 500 (9 bits) you need to redefine your "cups" as words and double your step size so that BX steps in word multiples, not bytes. And, uh, then you can't "XOR [Cup+bx],bx" because BX is twice what it should be, so you need a different register to step. How about SI, you don't seem to be using that one. The first pass will load each "cup" with its numeric value 1..500 and subsequent passes will run the process.

To extract primes, all you need to do is (after the very first pass) NOT run the inner loop if the FIRST "cup" of that loop is zero. You should finally be left with all "cups" zero except those whose index is a prime number - and maybe it's the non-zero indices, not the contents, that are your result. What this process is, very simply, is long division where the divisor is subtracted and the "cup" is left with the remainder. You are factorizing each number in turn with each possible number, and the only ones left at the end are those with no factors - ie, primes.