Jump to content

This site uses cookies. By continuing to browse the site you are agreeing to our use of cookies. Find out more here. X
X


Photo

List Factors of a Number


  • Please log in to reply
7 replies to this topic

#1 NELyon

NELyon

    Do you wanna brew my avatar?

  • Active Members
  • PipPipPipPipPipPip
  • 3,526 posts

Posted 13 November 2008 - 02:14 AM

Just a quick tool I whipped up.

AutoIt         
Global $nData $hGUI = GUICreate("Factorizr", 524, 154, 240, 142) $hNumber = GUICtrlCreateInput("25", 16, 40, 497, 21) $Label1 = GUICtrlCreateLabel("Number to get factors of:", 192, 16, 300, 17) $Label2 = GUICtrlCreateLabel("", 224, 80, 200, 17) $hFactors = GUICtrlCreateInput("", 16, 96, 497, 21) $hCopy = GUICtrlCreateButton("Copy to Clipboard", 120, 128, 105, 17, 0) $hFactor = GUICtrlCreateButton("Get Factors", 250, 128, 105, 17) ControlFocus($hGUI, "", $hFactor) GUISetState(@SW_SHOW) While 1     $nMsg = GUIGetMsg()     Switch $nMsg         Case -3             Exit         Case $hCopy             ControlFocus($hGUI, "", $hFactors)             ClipPut(GUICtrlRead($hFactors))         Case $hFactor             $nNumber = Int(GUICtrlRead($hNumber));             GUICtrlSetData($hFactors, "Working...")             $azFactors = _GetFactors($nNumber)             If IsArray($azFactors) Then                 GUICtrlSetData($hFactor, "Working...") ;~              ConsoleWrite("->Debug Output: $azFactors[0] = " & $azFactors[0] & @CRLF)                 For $i = 1 to $azFactors[0] ;~                  ConsoleWrite("->Debug Output: $azFactors[" & $i & "] = " & $azFactors[$i] & @CRLF)                     $nData &= $azFactors[$i] & ", "                 Next                 If $azFactors[0] = 2 Then                     GUICtrlSetData($Label2, "Factors for " & $nNumber & " (Prime):")                 Else                     GUICtrlSetData($Label2, "Factors for " & $nNumber & " (Composite):")                 EndIf ;~              ConsoleWrite("->Debug Output: $nData = " & $nData)                 GUICtrlSetData($hFactors, StringTrimRight($nData, 2))                 $nData = ""                 GUICtrlSetData($hFactor, "Get Factors")             Else                 ConsoleWrite("->Not an array? _GetFactors produced: " & $azFactors & @CRLF)             EndIf     EndSwitch WEnd Func _GetFactors($iInteger)     Local $azFactors[1], $nFactors = 0     If not IsInt($iInteger) Then         Return -1 ;Number is not an integer     EndIf     For $i = 1 to $iInteger         If Mod($iInteger, $i) = 0 Then                 $nFactors +=1                 Redim $azFactors[$nFactors+1]                 $azFactors[$nFactors] = $i         EndIf     Next     $azFactors[0] = $nFactors     Return $azFactors EndFunc


Pretty self explanatory.

Edited by KentonBomb, 18 November 2008 - 10:47 PM.








#2 NELyon

NELyon

    Do you wanna brew my avatar?

  • Active Members
  • PipPipPipPipPipPip
  • 3,526 posts

Posted 18 November 2008 - 10:47 PM

Small update to tell you whether or not your number is prime or composite.

#3 Wus

Wus

    Indentured Servant

  • Active Members
  • PipPipPipPipPipPip
  • 513 posts

Posted 19 November 2008 - 05:50 AM

I realize that you aren't really going for algorithm optimization... but if you think about it for a half second I think you'd see that you only need to loop from 1 to ceil(sqrt(n)) to find all factors. It can make a big difference in speed for larger n.

#4 NELyon

NELyon

    Do you wanna brew my avatar?

  • Active Members
  • PipPipPipPipPipPip
  • 3,526 posts

Posted 20 November 2008 - 12:42 AM

I realize that you aren't really going for algorithm optimization... but if you think about it for a half second I think you'd see that you only need to loop from 1 to ceil(sqrt(n)) to find all factors. It can make a big difference in speed for larger n.


Wouldn't that only list the factors that are less than sqrt(n)? That is what I expected, and that is also what happened when I tried it.

#5 Malkey

Malkey

  • MVPs
  • 1,523 posts

Posted 20 November 2008 - 09:40 AM

Wouldn't that only list the factors that are less than sqrt(n)? That is what I expected, and that is also what happened when I tried it.

Your script could be misleading to someone who just wants the factors of a number. That is, a lot of numbers when multiplied together equals that number.

Your script does not return the factors of a number.
Your script returns a list of whole numbers, each number being a single factor of a number

Enter 16 in your script and it returns, "1, 2, 4, 8, 16"

But, "1, 2, 4, 8, 16" are the factors of 1024

1 is a factor of every number
2 is a factor of 16
4 is a factor of 16
8 is a factor of 16
16 is a factor of 16
Each and every number in the list is a factor of 16

Now,1 and 16 are the factors of 16
1, 2, 8 are the factors of 16
2.5 and 6.4 are the factors of 16

But, 1, 2, 4, 8 are NOT the factors of 16
2 and 16 are NOT the factors of 16

Polynomial, x^2 - 4, factors are (x - 2) * (x + 2) [From Wikipedia (en) - Factorization]

When the factors of a number / object are multiplied together, the result is that number / object

So one has to realize the factors that make factors, factors, and the difference between the factors of a number and a factor of a number.

And that's a fact.

Maybe someone else could express that better, clearer, more understandable. If you can understand in the first place what I'm on about.

#6 JRowe

JRowe

    Chasing the white rabbits

  • Active Members
  • PipPipPipPipPipPip
  • 1,765 posts

Posted 20 November 2008 - 11:09 AM

He's calculating the factors, you're talking about polynomials. Similar, but not identical; he is correct.

You are correct, too, but far and above what the particular tool in this thread is about. 2.5 and 6.4 are the polynomial factors of 16 for that equation, but have no relevance to the general sort of factor he's talking about.

For that matter, the digits 1,2,3,4,5,6,7,8,9 and 0 are the factors of the set of decimal integers, where 0,1 are the factors of binary. Factors, the word, encompasses the set of all logical abstractions symbolizing the building blocks or atomic concepts comprising said set. This happens to be the whole number, numeric factorization of integers. Factors are confusing, if you don't make certain assumptions about what you're about. :mellow:

Neat script, btw.

#7 trancexx

trancexx

    Queen F. Elizabeth MCXI

  • Active Members
  • PipPipPipPipPipPip
  • 6,243 posts

Posted 20 November 2008 - 01:18 PM

Problem is caused by usage of the word "factor". Possibly more correct would be to use "divisor" (opposite of "multiple")

btw, negative divisors are missing, if you want all of them.

          ......       ......
        .:oOOOOo:.   .:oOOOOo:.
      .:oOO:'':Oo:. .:oO:'':OOo:.
     .:oO:      'Oo:oO'      :Oo:.
     :oO:         'o'   
      :Oo:
     :oO:                     :Oo:
     ':oO:     OT9AO0IEDrk   :Oo:'
      ':oO:                 :Oo:'
        ':oO.             .Oo:'
          ':oO
.         .Oo:'
            ':oO.     .Oo:'
              ':oO. .Oo:'
                'oO:Oo'
                  'o' :kiss:



 

.
eMyvnE


#8 Wus

Wus

    Indentured Servant

  • Active Members
  • PipPipPipPipPipPip
  • 513 posts

Posted 21 November 2008 - 02:52 AM

If your algorithm generates that y is a factor of z then it follows that z/y is an integer and is thus a factor you get for 'free'. (I use free to mean that you can find it in constant time, big-O(1).) And for any given pair of integers (x,y) where x*y=n, either x<=sqrt(n) XOR y<=sqrt(n). This follows since if you let both numbers be an epsilon larger than sqrt(n) than you cannot have the condition that x*y=n. e.g. (sqrt(n)+e1)*(sqrt(n)+e2) = n + sqrt(n)(e1+e2) + e1*e2 = n, and this can only be true if e1 or e2 is negative, which proves the point.

So loop thru ceiling(sqrt(n)) and then use the list of factors below sqrt(n) to generate their corresponding factors greater than sqrt(n).


Here's a simple version of what I mean...
Func getDivisors($n)     Local $i = 1     Local $sqrt_n = Ceiling(Sqrt($n))     ConsoleWrite("Factors of " & $n)     For $i=1 to $sqrt_n         If Mod($n, $i)=0 Then             ConsoleWrite("(" & $i & "," & $n/$i & ")")         EndIf     Next     ConsoleWrite(@CRLF) EndFunc



Also, something more interesting might be to get the prime factorization of the number, though to be fair no-one has ever asked for or needed that in these forums (to my knowledge).

Edited by Wus, 21 November 2008 - 02:56 AM.





0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users