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:
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.
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.
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
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
Quote from: AeroASM on November 12, 2005, 02:36:01 PM
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 =(.
If you don't know how to build an array, just display the factor in step 2.
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?
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...
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.
Or you could just print out each factor as you find it :U
Quoteinclude \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~!
Quote
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 !
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
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 :'(