Find # factors for number.

I designed a system meant to find a number of numbers which may be multiplied to get a pre-unknown value. The one I made however, is not good enough, since it times out at the 1121 check(on my first test), and has to go through 533,794,816 checks just for a 4 factor number.

I was curious if anyone had a better way to find a certain number of factors no greater then a certain number, in this test the number was 152, so if the value needed was greater than 152, then it would look for 2 factors, if greater than 152 X 152, it would look for 3, and etc.

Please describe the application.

It simply goes through every possible combination of number, If (Integer A) X (Integer B) X (Integer C) X (Integer D) = Value then run valuefound actions, else keep looking.

After posting this though I realized that not every number may be reachable this way, so i created a small trigger meant to find all of these and it came out to be 82% unreachable.

I will have to find a new way to get more accurate values, but my above problem still stands, and thanks for caring to read .

What is the problem you are trying to solve...

I think the problem is that he wants his function to run faster or make it so that it doesn't time out. I'd suggest posting the function that you are having trouble with and explain the problem a bit more since I also don't quite understand the problem.

I need a completly different method to do it, the one I have would be impossible to optimize that much.

I need to find a certain number of factors of a value. If the value was 180, and the number of factors needed was 2, then factor1 could be 60, and factor2 could be 3. 60X3 = 180. The factors cannot be higher then a certain number, in this case 152.

I originally tried to do it by checking every possible combination with something like this... But since this needs to do that up to 23,000 times(152X152), it times out, and it also needs to be able to find the 3, 4, 5, or more factors for much larger numbers.

I'm trying to write a save-load code system for my map, and this requires it. My other comment was about how I just discovered A X B where 0 > A or B < 152 can only equal 18% of the numbers between 1 and 23,000.

There are many, many algorithms for factoring integers. I'm a little speechless at the method you've arrived at. Warcraft has a division operator. When used on two integers, it tells the quotient. To get the remainder of x/y, you can use a formula like "x - (x/y)*y". When this is zero, x is divisible by y. So you can iterate y from 1..sqrt(x) until you find a factor. If you find none, it's prime. Since you only need to check divisibility with primes, you can skip all the even numbers. Since you only need 152, you could fill an array up with the primes up to there and just iterate through them.

However, I strongly suspect that you do not want to factor integers at all. I am guessing you are trying some sort of reduction to base 152. It's interesting because multiplication is commutative so you can scramble the output in any order. Unfortunately, as you have noted, there are prime numbers and numbers with more than four factors above 152. So this could never work.

I'm using a base 76, but for every 6-7 characters I add a additional character which holds a boolean for each character, thus doubling it. This actually comes out to a little less possible combinations, but I think it will work well for the save code.

The new method I came up with is to have one character which holds a integer from 1 - 152, and a second character which holds a real value from -.500 to .500(spread out by 1000/NumOfChars). The integer would be converted to a real, and the second a modifier to it to find the closest value possible to the desired value, by multiplying the sum by itself. I haven't thought of a way to do this without timing out the game again however, and it won't be exact but close enough.

For the division operator you recommended to use, I don't see how this would help as I would have to still go through every possability. Maybe i'm just a little slow .

Alright let's suppose we want to encode three pieces of information.
First we have the level of the hero. It goes from 1-3. Let's relabel these 0-2.
Second we have the weapon he is carrying. There are two weapons. Let's relabel these 0-1.
Finally, his class. It goes from 1-4. Let's relabel these 0-3.

Now, we want to create a cartesian product of these three pieces of information. We want a way to encode the three of these numbers into a single number. First off, how many items does the product set have? For each level of the hero, we have 2 weapons. For each class, we have 3 levels. so we have 4*3*2 total states. Let's arrange them in a line, with class on row 1, weapon on row 2, and level on row 3 and on the bottom, the index of the state
In order to make our save code, we need several mappings:

• (c,w,l) -> s
  This converts our game data into a save state. We use this while saving.
• s -> (c,w,l)
  This converts a save state back into game data. We use this while loading.
• s -> ascii
  This converts a save state into a string.
• ascii -> s
  This converts a string back into a save state

There are many ways to do this mapping. The optimal method is to use multiplication and division. Convince yourself that:

• (c,w,l)->s
  
  Code:

  s = l+lmax*(w+wmax*(c))

• s->(c,w,l)
  
  Code:

  l = s mod lmax
  s = s / lmax
  w = s mod wmax
  s = s / wmax
  c = s

"x mod y" means "x - (x/y)*y"

What we are doing is taking our state at one point, shifting it past the highest number we might want to encode at this point, then placing our number in the slot.
One difficulty with this approach is that the machine integers can only easily store 31 bits (31 0-1 choices). This is around 5 characters worth of information. Longer save codes need some sort of work around for this.

The same process is used for breaking the save state down into ascii. In this case we have a fixed multiply/divide shift.