Listing Factors of a Non Prime number

[gusto]

as said in my last post... new project =)... it involves my last project which i finally got to work.. http://www.masmforum.com/simple/index.php?topic=3057.0... the prof. asked us to use our previous project, to find the factors of a Non Prime number... such as 300, factors would be: 2 2 3 5 5 (thats the example he gave us)... how do i go about doing this? i can get the first factor of any number with my program, but how can i make it go to the next? my program is posted on the link above... i have been playing with it, but no luck.. where should i start? thanks again!! u guys are great  :dance:

[sluggy]

This is very simple.... your prime number program finds numbers that only have two factors - the number itself and 1. Which means that everything you try to divide it by will have a remainder, therefore you know it isn't a factor. If there is no remainder, then that number must be a factor of the number you are testing it against. I haven't looked at your program, but all that should be required is a simple change to a comparison/jump pair.

[tenkey]

It looks like your prof is asking you to find all of the number's prime factors. When you divide a nonprime number by one of its prime factors, the quotient is the number that contains all the other prime factors.

[AeroASM]

Algorithm to prime factorise N:

1. Find the smallest prime factor of N
2. Add it to your list
3. Divide N by the prime factor
4. If N=1 then exit
5. Jump to step 1

[thomasantony]

Hi,
  I will give another no so small algo. First try dividing the numebr by 2. If yes, add two as one of the  factors

1. Put N=3
2. Divide number by N
3. If divisible check whether N is prime
4. If yes display(or do whatever you want to do with it) else go on to step 5
5. Increment N by two.(n even number other than 2 is prime)
6. If N == sqrt(number) exit
7. goto Step 2

Hope this helps!!

Thomas :U

[gusto]

Algorithm to prime factorise N:

1. Find the smallest prime factor of N
2. Add it to your list
3. Divide N by the prime factor
4. If N=1 then exit
5. Jump to step 1

how do i form that list? array, or just putting the numbers in a register? i dont know how to build an array =(.

[tenkey]

If you don't know how to build an array, just display the factor in step 2.

[sluggy]

gusto,
It seems there are a couple of different interpretations on the requirements of your assignment - can you be more specific about what you want?

[gusto]

word for word:

Our 4th project is to extend Proj.3 to factoring number, that is to find all prime factors including multiplicities. That is, if the number is 300, 1, and 109, the output should be:
300  2 2 3 5 5
1
109 109

As usual, begin by printing a suitable title and skip a line. Then read an integer into double word, and then factor it. If the number is 0, then exit the program.
-----------------------
thats my assignment... ive been tryin to figure it out with no luck.. my prime number program is posted on the link above.. can anybody see what i should add/take out? i was tryin to do what AeroASM was telling me to do, but i was just getting one factor still, i dont seem to be doing it the right way  :dazzled: ..... thx in advanced...

[NPNW]

Gusto,

You have to think what the process is that you are trying to do.

You are going to need to declare space for your initial number 300.
Then what do you do?

the next step is to find a factor of 300. Example 2. 300/ 2 is 150.
The 2 must be placed in a memory location as this is one of the factors.
You should make a place where you can put a whole list of factors.
The remainder is 150. Can 150 be divided by 2 again without any remainder?
150/2 is 75.
Again store the 2. place the 75 in the number we are dividing.
Can 75 be divided by 2 with nothing left over?
75/2 =37.5. Not a factor.
Increment to the next number 3.
75/3 =25.
save the 3 in our list of factors. save the 25 in the number we are working on.
Is 25/3 a whole number?
25/3 = 8.33. Not whole move to next number.
25/4 = 6.25. Not whole move to next number.
25/5 = 5. Again save the 5 as this is the number we are working on.
save 5 in our list of factors.
Does 5 = 5. Yes. Then save the number we are working on in our list of factors.
display the list, and exit.

You need a variable for your number you are working on.
You need a variable for your current factor.
You need a variable to hold the intermediate value.
You need a list of factors.
You need several loop routines to implement the steps above.
You need a routine to print out or display your variables.

Good Luck hope this helps.

[zooba]

Or you could just print out each factor as you find it  :U

[gusto]

include \masm615\include\irvine16.inc


               .data
x               dword     300
z               dword     2
k               dword     3

intro           byte     "Testing for prime factors.",0
space           byte     " ",0
sign            byte     " = ",0

                .code
                main     proc

                startup
                cmp     x,1
                jz      x_is_1
                mov     edx,offset intro
                call    writestring
                call    crlf
                call    crlf
                cmp     x,3
                jz      x_is_3
                mov     ecx,99999
                mov     ebx,z
                mov     eax,x
                call    writedec
                mov     edx,offset sign
                call    writestring
   

      
test1:          mov     eax,eax
                xor     edx,edx
                div     ebx
                cmp     edx,0
                je      ifnotprime1
                jmp     test2

ifnotprime1:    mov     edi,eax   
                mov     eax,ebx
                call    writedec
                mov     edx,offset space
                call    writestring
                inc     ebx
                cmp     eax,ebx
                jz      x_is_1
                mov     eax,edi
                jmp     test1
      

ifnotprime:     mov     edx,offset space
                call    writestring
                mov     eax,eax   
                call    writedec
                mov     edx,offset space
                call    writestring
                mov     eax,k
                call    writedec
                call    crlf
                exit

      
itisprime:      mov     eax,x
                call    writedec
                mov     edx,offset space
                call    writestring
                call    crlf
                exit

test2:          mov     eax,eax
                xor     edx,edx
                div     ebx
                cmp     edx,0
                je      ifnotprime
                cmp     eax,z
                jb      itisprime
                add     k,2
                loop    test2
   
      
x_is_3:         jp      itisprime
x_is_1:         exit


      exit
main            endp
                end     main

thats what i edited my code to, and its not very helpful now, my head is hurting from tryin to figure it out... now when i put a number like 109, instead of giving me 109 = 109, i get 109 = 27 3..... and for 300 i get 2 3  3 3..

can anybody try to point out where the errors are? i feel like i should even rewrite my prime number program and go at it from scratch, but becuase of time constraints i cant... any help like always is appreciated , thank u~!

[gusto]

include \masm615\include\irvine16.inc


      .data
x      dword      300
z      dword      2
k      dword      3

intro      byte      "Testing for prime factors.",0

space      byte      " ",0
      .code
      main      proc

      startup
      cmp      x,1
      jz      x_is_1
      mov      edx,offset intro
      call      writestring
      call      crlf
      call      crlf
      cmp      x,3
      jz      x_is_1
      mov      ecx,99999
      mov      ebx,k
      mov      edi,z
           mov      eax,x


test1:      mov      eax,eax
      xor      edx,edx
      div      z
      cmp      edx,0
      jne      test2
      mov      edi,edi
      call      writedec
      mov      edx,offset space
      call      writestring
      cmp      eax,edi
      je      x_is_1   
      loop      test1
      







test2:      mov      eax,eax
      xor      edx,edx
      div      ebx    ;3
      cmp      edx,0
      jz      test1
      add      ebx,2
      div      ebx
      cmp      edx,0
      jne      test2
      mov      ebx,ebx
      call      writedec
      mov      edx,offset space
      call      writestring
      cmp      eax,ebx
      je      x_is_1      
      loop      test2
      
x_is_1:      exit
      
      
      exit
main      endp
      end      main

i tried to rework the program more or less from scratch.. test1 being for my 2's, and test2 for my odd numbers(3,5,7,..), and i seem to be getting an infinite loop.. any thoughts on if doing it the right way or not really? ima keep working on it, but id love feedback.. thanks !

[subhadeep_ghosh]

Gusto....NPNW's algo was correct... :U

I'll give you the idea but it's upto you to implement it.... :wink

Let's say you want to find out all the prime factors of the number stored in the variable NUM...
Let upper_limit = NUM / 2
Let divisor = 2

while divisor <= upper_limit

  while true

    if (NUM % divisor) == 0 then

      print the divisor or store it somewhere

      NUM = NUM / divisor

    else

      jump out of the inner while loop

    end the if

  end inner while

  divisor = divisor + 1

end outer while

Thatz the best I could do to help you out.... :bg ...
I have added those extra blank lines to make you feel how long the actual assembly code would be... :U

[gusto]

the algorithm isnt wat confuses me, i know the pseudo code to it.. its just the actual assembler code that messes me up... my prof. doesnt teach assembler, he jus writes what the books says word by word, and when i ask him questions he doesnt know how to answer.. that is why my programs may have alot of extra stuff i dont need, and dont work efficiently, tho they do work.. for my current project im just getting infinite loops and other random problems that my prof. doesnt know how to help me, he just wants printed results and the code to go along with them... so im still tryin to go by the algorithms you guys gave me, but im not to great with asm code  :'(