ID:165899
 
Does anyone have some clever algorithm to get a list of all the factors of a number? So I could do something like:

mob/verb/Factors(n as num)
var/list/L = getfactors(n)


And if n was 12, L would contain "1,3,4,6,12" (I don't really want negative numbers - I don't even know if they count as factors or not).

I can't really think of any smart way of doing it, all that comes to mind is something like:

proc/getfactors(n)
var/list/result = list()
for(var/i=1,i<=n,i++)
var/a = n/i
var/b = round(a)
if(a==b)
result += i
return result
Heh. Factorization is a "hard" problem. If you had a clever algorithm for it, you'd definitely win some sort of math/computer science prize.

There are, however, ways of making a factorization algorithm that is not quite as slow. Somewhere on the internet is an excellent site, which I sadly don't have a bookmark to. :(

A few of the tricks on that site included first checking for 2 specifically, then skipping even numbers from then on. There were also a few binary-related things to help look for multiples of 3 and some other similar numbers.
In response to Jon88
One thing that might speed the process considerably: As you increment i, if it's a factor, then n/i is also a factor. Then the ceiling of your loop can be the square root of n.

Code removed for the sanity of BYONDers. See EDIT below.


The result is unsorted, but contains all the factors. The code is untested, because I only have about 5 minutes left here.


EDIT: The demo code I posted here was crap. Use Post [link] instead. Never post without testing. ;)
try using


if i=n
//there are no more
else
if n%i = 0 add it as a factor,
else i++ and start over
In response to Bones the Great
I don't think you understand, so don't try to help. You even forgot the double == in an if statement.
In response to Pyro_dragons
He wasn't writing in DM, he was merely demonstrating the concept in what I think is called pseudocode. And his method makes sense but I'm not sure if it's any faster than mine.
In response to Bones the Great
Do you want all factors, or prime factors?

Here are some procs I just came up that return factors. I am sure it could be optimized more. It really doesn't need to be complicated. Sifting out non-prime numbers from the search would not do what you want, if you do want all possible combinations which result in the given number. However, sifting out non-prime numbers may help with finding prime factors, but not a lot with the range possible in Byond. (For a prime number finder try: Post [link])

If you want prime factors:
proc/Prime_Factor(n)
var/list/factors = new()
var/i = 2 //1 isn't a prime number
while( i < sqrt(n) ) //No need to check past the square root of the number
while( !(n%i) ) //If the number evenly divides into the original number
n /= i //Divide it out and set the new number to n
factors += i //Add the divisor to the factors list
i++ //Increment I
factors += n //You have to include the remaining number, (it will be prime)
return factors


If you want factors as in, two number multiplied together which will equal the original number, how about this:

//Simple Way. (Basically what you did, but using modulus operator.)
proc/Factor(n)
var/list/factors = new()
for( var/i=1, i <= n, i++ )
if( !(n%i) ) factors += i
return factors

//Or if you want them organized in sets
proc/Factor(n)
var/list/factors = new()
for( var/i=1, i <= sqrt(n), i++ )
if( !(n%i) )
factors += list(i,n/i) //Adds the factor and its partner factor to the list
return factors


I have tested these and they seem to work. I don't know if they are any faster or slower than the others. I hope you understand the idea behind them. The second one is basically what Bones The Great gave as an example. You basically had the right idea in your example, but it is better to make use of the modulus operator "%" which gives the remainder of the division of two numbers. So if numbers divide evenly into each other, then there is no remainder.

(Sorry if this doesn't make sense I am half-asleep.)
In response to Shadowdarke
;_; My brain hurts.

What purpose do you want prime numbers for anyway? :|
In response to CuriousNeptune
I don't want prime numbers, I want factors. And my reason is because I need to use them in my damage formula for my fighting game.
In response to Shadowdarke
Thanks.

But is there any way to have the list automatically sorted because that's fundamental to the game I'm making. I could use a sorting algorithm on it but I'm not sure if the time taken to get the factors and sort them would be less than using my method.
In response to DeathAwaitsU
DeathAwaitsU wrote:
Thanks.

No problem. :)


But is there any way to have the list automatically sorted

Sure. Since the n/i factors will be generated in reverse order, just keep a seperate list of them and add the reverse list to the result at the end.

Here is an updated version of the proc; tested, accurate, and returns factors in order.
proc/getfactors(n)
if((n<=0) || (n != round(n))) return
if(n == 1) return list(1)
var
ceiling = sqrt(n)
start = 2
increase = 1
list
result = list(1)
result_end = list(n)
if(n%2) // 2 is not a factor
start = 3
increase = 2
for(var/i=start, i<ceiling, i+=increase)
if(!(n%i))
result += i
result_end += n/i

// add ceiling if appropriate
if(ceiling == round(ceiling)) result += ceiling

// add the other end of the list
for(var/index = result_end.len to 1 step -1)
result += result_end[index]
return result


It's considerably faster than a simple loop like "The Simple Way" Drumersl posted. I profiled each of them, factoring every integer from 1 to 10,000. The above snippet took 0.422 seconds. The Simple Way took 27.313 seconds.
Assuming you have a quicksort proc implemented, this will do nicely:
proc/Factors(n)
var/a,b,c,list/F
for(a=1,!n%(a*2),a*=2)
if(a>1)
b=round(n/a,1)
F=Factors(b)
.=list()
for(,a,a=round(a/2))
for(b in F)
.+=b*a
QuickSort(.)
return
b=round(sqrt(n),1)
if(b*b>n) --b
for(a=b,a>2,--a) if(!n%a)) break
if(a<=2)
if(n<=1) return list(1)
return list(1,n)
b=round(n/a,1)
.=lis()
for(a in Factors(a))
for(c in Factors(b))
.+=a*c
QuickSort(.)


Lummox JR
In response to Lummox JR
Thanks, this one seems faster than Shadowdarke's.

Would you mind explaining how/why it works?
In response to DeathAwaitsU
DeathAwaitsU wrote:
Thanks, this one seems faster than Shadowdarke's.

Would you mind explaining how/why it works?

Well basically, by taking the sort out of the actual algorithm workings itself, you have more freedom to explore it. Simply searching through the possible factors for a number is usually not a very helpful thing to do, but by finding factors recursively you can speed up the whole process.

For example:
180 = 4 * 45 = (1,2,4) * 45
45 = 5 * 9 = (5) * 9
9 = 3 * 3 = (1,3) * (1,3) = (1,3,9)
45 = (1,3,9,5,15,45) = (1,3,5,9,15,45)
180 = (1,2,4) * (1,3,5,9,15,45) = (1,2,3,4,5,6,9,10,12,15,18,20,30,36,45,60,90,180)

Lummox JR