Prime Number Program

[dedndave]

it is because the step changes with each pass of the outer loop
the first time through, it steps by 2 (i.e. marking elements that are divisible by 2)
the second time through, it steps by 3 (i.e. marking elements that are divisible by 3)
the third time through, it steps by 4 (i.e. marking elements that are divisible by 4 - which have already been marked - lol)
and so on
we skip the first pass on the inner loop, that way, it does not mark the prime, itself

[veronicak5678]

OK, I get it. I will try to translate this to my level.

Thanks again, Dave. I feel like you're my second (and better) teacher!

[ilian007]

Dedndave I agree with the last post of Veronica :)

[dedndave]

hey - at least your prof isn't a meanie
if he was mean, he would have given you the primes program already written and asked for squares - lol
look for that on the final exam, eh ?

[ilian007]

He is a very smart and good guy and knows a lot. I think he is so bored of teaching so easy things which are defin. not so exciting for him :) I am trying to create an easy way to produce primes. Your way is great dedndave, but too advanced for me as well :)

I am trying to integrate an extra array in my inner loop which will count the skiped elements (indexes) by Y for all X's

y=(2),4,6,8,10,12,14,16,18,20,22 
y=(3),6,9,12,15,18,21
y=(4),8,12,16,20,24

for those 3 - 1,3,5,7,11,13,17,19 were skipped and all them are primes.

I am trying to pull out all the elements which were NOT XORed by AL

LOOP_Y: 
   XOR     MyArr[DI-1],AL
   ADD     DI,CX
   CMP     DI,500
        JB      LOOP_Y 


Should I put all them in array and then pull all all the 0 elements of the new array ?

shouldnt be so complicated I guess ?

[dedndave]

just look at the program i posted
take careful note of the differences between the SQUARES and PRIMES routines
those are the lines that i have commented
in that program, i started the PRIMES routine with an all 1's array - so set it to 1 for an all 0's array

[MichaelW]

In my test doing the P(n) = n2 + n + 41 with the FPU required 9 additional instructions, and no additional data. In the few hours I spent on it I could not find any way to switch the output to primes by changing only a few instructions.

[dedndave]

look on page 2, Michael

[Rockphorr]

Solution is

Code Select Expand

;===================================================================
         EXTERN  NEWLINE:FAR
         EXTERN  PUTDEC:FAR
         EXTERN  putstrng:FAR
;===================================================================
INCLUDE PCMAC.INC
.MODEL  SMALL
.586
        .STACK  512
        .DATA
CUPS DB 500 DUP (0)
CUP DB 0
X DW 2 ;<------------------------------------------------------point 1
Y DW 1
Z DW 0       
;---------------------------------
.CODE
MARBLES   PROC
        MOV     AX,DGROUP           ;SET DS-REGISTER TO POINT TO
        MOV     DS,AX               ;DATA SEGMENT
        MOV     ES,AX   
XLOOP:
MOV CX, 500
CMP X, CX
JGE XDONE
MOV CX, X
MOV Y, CX
YLOOP:
MOV CX,500 
CMP Y, CX
JGE YDONE ;STOP WHEN X > 500
DEC Y ; ELEMENT 0
MOV DI,Y
CMP [CUPS+DI],0
JE ONES
MOV [CUPS+DI], 0
MOV CX, X
ADD Y, CX
INC Y
JMP YLOOP
ONES:
MOV [CUPS+DI], 1
MOV CX, X
ADD Y, CX
INC Y
JMP YLOOP
YDONE:
INC X
JMP XLOOP
XDONE:
MOV DI, 500
CMP Z, DI
JGE ENDPROGRAM
MOV DI, Z
CMP [CUPS+DI],1
JE PRINT
JMP ZEROS
PRINT:

MOV AX, DI
ADD AX,2  ;<---------------------------------------------------------------------------------point 2 
CALL PUTDEC
CALL NEWLINE
ZEROS:
INC Z
JMP XDONE
ENDPROGRAM:

.EXIT
        MOV     AX, 4C00H
        INT     21H
MARBLES   ENDP
        END     MARBLES


OUOU!!!!!!!!!!!!!!!!! YES IT IS HIM !!!!!!!!!!!!!!!!   :clap: :clap: :clap: :clap: :clap: :clap: :clap: :clap: :clap: :clap: :clap: :clap: :clap: :clap: :clap:

[dedndave]

guys ! - lol
http://www.masm32.com/board/index.php?topic=12705.msg98049#msg98049

[Rockphorr]

guys ! - lol
http://www.masm32.com/board/index.php?topic=12705.msg98049#msg98049

:thumbu
BUT
change few lines is not mean replace parts of code to subroutines
:dance: :dance: :dance:

[dedndave]

i did that so that both the unmodified and modified code could be run together - lol
that way, you can see the changes - and see the results of both at runtime

;------------------------------------------------------

SQUARES PROC    NEAR

;BUILD THE ARRAY WITH SQUARES

;OUTER LOOP

        MOV     CX,AX               ;START WITH 1

XLOOP:  MOV     DI,CX

;---------------------------------

;INNER LOOP

YLOOP:  XOR     ARRY[DI-1],AL       ;TOGGLE IT
        ADD     DI,CX
        CMP     DI,SI
        JBE     YLOOP

;---------------------------------

        INC     CX
        CMP     CX,SI
        JBE     XLOOP

        RET

SQUARES ENDP

;------------------------------------------------------

;------------------------------------------------------

PRIMES  PROC    NEAR

;BUILD THE ARRAY WITH PRIMES

;OUTER LOOP

        MOV     CX,2                ;START WITH 2

ALOOP:  MOV     DI,CX
        JMP SHORT NEXTB             ;SKIP THE FIRST ONE

;---------------------------------

;INNER LOOP

BLOOP:  MOV     ARRY[DI-1],AH       ;DON'T TOGGLE IT - RESET IT

NEXTB:  ADD     DI,CX
        CMP     DI,SI
        JBE     BLOOP

;---------------------------------

        INC     CX
        CMP     CX,SI
        JBE     ALOOP

        RET

PRIMES  ENDP

;------------------------------------------------------

[MichaelW]

Dave,

Your solution works fine, but IMO it's too far from the original algorithm. Going from a straightforward implementation of the original algorithm in assembly to your prime code requires changes to more than "a few lines". And I have doubts that the instructor would expect a beginner, already more or less overwhelmed with the assembly code details, to start with the original algorithm and arrive at something like yours.

[dedndave]

are you talking about the code or the pseudo-code ?
the pseudo-code was the assignment of the instructor
the original assembler code was written by the student
to arrive at the code i used, i merely simplified her original code
i also reorganized it, for a few reasons, primarily to give the student an example to learn from
part of the goal was to help the student write cleaner, more efficient code in the future

EDIT - i am looking at the pseudo-code and trying to see how my code does not match it ?????

All he told us was we had to use the following pseudo-code:

arr 500 dup(0)

for x = 1 to 500
     for y = x to 500 step x
        if arr(y) = 0
            arr(y) = 1
        else
            arr(y) = 0
       endif
     next y
next x

then to print:

for x = 1 to 500
    if arr(x) = 1
    print x
  endif
next x

[dedndave]

One way to go from squares to prime numbers (within limits) would be this:
P(n) = n2 + n + 41

In my test doing the P(n) = n2 + n + 41 with the FPU required 9 additional instructions, and no additional data.

(can't use my code - lol - but the FPU is ok)

a quote from your link:

Euler noted that the function
    n2 + n + 41
gives prime numbers for n < 40 (but not necessarily so for bigger n)

http://en.wikipedia.org/wiki/Prime_number#Distribution

i think the real issue is this, Michael
the instructor did not use "your" algorithmm and.....

In the few hours I spent on it I could not find any way to switch the output to primes by changing only a few instructions.

i won't help these students any more - i can see that you have it covered