Sign in to follow this  
Followers 0
PsaltyDS

Return all factors of an integer

6 posts in this topic

#1 ·  Posted (edited)

I wanted a function to return all factors of an integer, which involves primality testing. Wikipedia search turned up techniques way over my head (not surprising), but their "Naïve methods" gave me this as a start:

#include <array.au3>

While 1
    $n = InputBox("Factorizor", "Input number to factor: ")
    If @error Then Exit
    $n = Number($n)
    $iTimer = TimerInit()
    $avRET = _Factor($n)
    $ErrSav = @error
    $ExtSav = @extended
    $iTimer = TimerDiff($iTimer)
    _ArrayDisplay($avRET, "Primes of " & $n & ", @error = " & $ErrSav & ", @extended = " & $ExtSav & ", " & Round($iTimer / 1000, 3) & "sec")
WEnd

; ----------------------------------------------------------------------
; Function:         _Factor()
; Purpose:          Return all factors of a signed integer
; Syntax:           _Factor($i)
;   Where:          $i = signed integer value
; Returns:          A 1D array with [0] = count of factors
;   On success:     [1] = 1 or -1 depending on sign of input $i, [2] thru [n] = prime factors
;                   If [0] = 2 (because the only factors are 1 or -1 and the number) then input was prime.
;   On failure:     [0] = 0 and sets @error
; Notes:            Based on the simplest "naive" prime number test, sped up some by inclusion 
;                   of a short prime number table.
;                   The number 1 is not normally given as a prime factor, but is included so 
;                   the function can handle signed/unsigned numbers in a predictable manner.
;                   Element [1] of the array will be 1 or -1 depending on the sign of the input.
;                   Returns @error for non-integer or 0 inputs.
; Author:           PsaltyDS at www.autoitscript.com/forum
; Version: 1.0.0 dated 28 December, 2007
; ----------------------------------------------------------------------
Func _Factor($i)
    Local $avRET[1] = [0]
    Local $iTest, $iWorking, $iOddNum
    
    ; Test for valid input
    If IsInt($i) = 0 Then
        SetError(1)
        Return $avRET
    ElseIf $i = 0 Then
        SetError(2)
        Return $avRET
    EndIf
    
    ; Check for negative number
    Local $avRET[1024] = [1, 1]
    If $i < 0 Then
        $avRET[1] = -1
        $i = $i * - 1
    EndIf
    $iWorking = $i
    
    ; Quick return for input = 1
    If $iWorking = 1 Then
        ReDim $avRET[2]
        Return $avRET
    EndIf
    
    ; Initial table of primes
    Local $avPrimes[201] = [200, _
            2, 3, 5, 7, 11, 13, 17, 19, 23, 29, _
            31, 37, 41, 43, 47, 53, 59, 61, 67, 71, _
            73, 79, 83, 89, 97, 101, 103, 107, 109, 113, _
            127, 131, 137, 139, 149, 151, 157, 163, 167, 173, _
            179, 181, 191, 193, 197, 199, 211, 223, 227, 229, _
            233, 239, 241, 251, 257, 263, 269, 271, 277, 281, _
            283, 293, 307, 311, 313, 317, 331, 337, 347, 349, _
            353, 359, 367, 373, 379, 383, 389, 397, 401, 409, _
            419, 421, 431, 433, 439, 443, 449, 457, 461, 463, _
            467, 479, 487, 491, 499, 503, 509, 521, 523, 541, _
            547, 557, 563, 569, 571, 577, 587, 593, 599, 601, _
            607, 613, 617, 619, 631, 641, 643, 647, 653, 659, _ 
            661, 673, 677, 683, 691, 701, 709, 719, 727, 733, _
            739, 743, 751, 757, 761, 769, 773, 787, 797, 809, _ 
            811, 821, 823, 827, 829, 839, 853, 857, 859, 863, _ 
            877, 881, 883, 887, 907, 911, 919, 929, 937, 941, _ 
            947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, _ 
            1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, _ 
            1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, _
            1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223] 
    
    ; Use static table of primes to start with
    For $p = 1 To $avPrimes[0]
        While 1
            $iTest = Mod($iWorking, $avPrimes[$p])
            If $iTest = 0 Then
                ; This is a factor
                $avRET[0] += 1
                $avRET[$avRET[0]] = $avPrimes[$p]
                $iWorking = $iWorking / $avPrimes[$p]
                If $iWorking = 1 Then
                    ; Last factor found
                    ExitLoop 2
                Else
                    ; Try same prime again
                    ContinueLoop
                EndIf
            Else
                ; This is not a factor, next prime
                ExitLoop
            EndIf
        WEnd
    Next

    ; Continue if remaining factors are larger than the static primes
    If $iWorking > $avPrimes[$avPrimes[0]] Then
        $iOddNum = $avPrimes[$avPrimes[0]] + 2
        While 1
            While 1
                $iTest = Mod($iWorking, $iOddNum)
                If $iTest = 0 Then
                    ; This is a factor
                    $avRET[0] += 1
                    $avRET[$avRET[0]] = $iOddNum
                    $iWorking = $iWorking / $iOddNum
                    If $iWorking = 1 Then
                        ; Last factor found
                        ExitLoop 2
                    Else
                        ; Try same odd number again
                        ContinueLoop
                    EndIf
                Else
                    ; This not a factor, next odd number
                    ExitLoop
                EndIf
            WEnd
            $iOddNum += 2
            If $iOddNum > Int(Sqrt($i)) Then
                ; Remaining number is prime = last factor
                $avRET[0] += 1
                $avRET[$avRET[0]] = $iWorking
                ExitLoop
            EndIf
        WEnd
    EndIf
    
    ; Resize the array and return
    ReDim $avRET[$avRET[0] + 1]
    Return $avRET
    
EndFunc   ;==>_Factor

The returned array may not be considered standard because for any valid input (a non-zero integer) it will have 1 or -1 as the first factor. The number 1 is not usually listed as a factor, but that seemed the most consistent way to handle negative numbers as inputs. Also, if $avReturn[0] = 2 then the input number was prime, making it a fair test for primality.

I'm looking into the more "non-naïve" methods for primality testing for future improvements.

:)

Edited by PsaltyDS

Valuater's AutoIt 1-2-3, Class... Is now in Session!For those who want somebody to write the script for them: RentACoder"Any technology distinguishable from magic is insufficiently advanced." -- Geek's corollary to Clarke's law

Share this post


Link to post
Share on other sites



I wanted a function to return all factors of an integer, which involves primality testing. Wikipedia search turned up techniques way over my head (not surprising), but their "Naïve methods" gave me this as a start:

#include <array.au3>

While 1
    $n = InputBox("Factorizor", "Input number to factor: ")
    If @error Then Exit
    $n = Number($n)
    $iTimer = TimerInit()
    $avRET = _Factor($n)
    $ErrSav = @error
    $ExtSav = @extended
    $iTimer = TimerDiff($iTimer)
    _ArrayDisplay($avRET, "Primes of " & $n & ", @error = " & $ErrSav & ", @extended = " & $ExtSav & ", " & Round($iTimer / 1000, 3) & "sec")
WEnd

; ----------------------------------------------------------------------
; Function:         _Factor()
; Purpose:          Return all factors of a signed integer
; Syntax:           _Factor($i)
;   Where:          $i = signed integer value
; Returns:          A 1D array with [0] = count of factors
;   On success:     [1] = 1 or -1 depending on sign of input $i, [2] thru [n] = prime factors
;                   If [0] = 2 (because the only factors are 1 or -1 and the number) then input was prime.
;   On failure:     [0] = 0 and sets @error
; Notes:            Based on the simplest "naive" prime number test, sped up some by inclusion 
;                   of a short prime number table.
;                   The number 1 is not normally given as a prime factor, but is included so 
;                   the function can handle signed/unsigned numbers in a predictable manner.
;                   Element [1] of the array will be 1 or -1 depending on the sign of the input.
;                   Returns @error for non-integer or 0 inputs.
; Author:           PsaltyDS at www.autoitscript.com/forum
; Version: 1.0.0 dated 28 December, 2007
; ----------------------------------------------------------------------
Func _Factor($i)
    Local $avRET[1] = [0]
    Local $iTest, $iWorking, $iOddNum
    
    ; Test for valid input
    If IsInt($i) = 0 Then
        SetError(1)
        Return $avRET
    ElseIf $i = 0 Then
        SetError(2)
        Return $avRET
    EndIf
    
    ; Check for negative number
    Local $avRET[1024] = [1, 1]
    If $i < 0 Then
        $avRET[1] = -1
        $i = $i * - 1
    EndIf
    $iWorking = $i
    
    ; Quick return for input = 1
    If $iWorking = 1 Then
        ReDim $avRET[2]
        Return $avRET
    EndIf
    
    ; Initial table of primes
    Local $avPrimes[201] = [200, _
            2, 3, 5, 7, 11, 13, 17, 19, 23, 29, _
            31, 37, 41, 43, 47, 53, 59, 61, 67, 71, _
            73, 79, 83, 89, 97, 101, 103, 107, 109, 113, _
            127, 131, 137, 139, 149, 151, 157, 163, 167, 173, _
            179, 181, 191, 193, 197, 199, 211, 223, 227, 229, _
            233, 239, 241, 251, 257, 263, 269, 271, 277, 281, _
            283, 293, 307, 311, 313, 317, 331, 337, 347, 349, _
            353, 359, 367, 373, 379, 383, 389, 397, 401, 409, _
            419, 421, 431, 433, 439, 443, 449, 457, 461, 463, _
            467, 479, 487, 491, 499, 503, 509, 521, 523, 541, _
            547, 557, 563, 569, 571, 577, 587, 593, 599, 601, _
            607, 613, 617, 619, 631, 641, 643, 647, 653, 659, _ 
            661, 673, 677, 683, 691, 701, 709, 719, 727, 733, _
            739, 743, 751, 757, 761, 769, 773, 787, 797, 809, _ 
            811, 821, 823, 827, 829, 839, 853, 857, 859, 863, _ 
            877, 881, 883, 887, 907, 911, 919, 929, 937, 941, _ 
            947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, _ 
            1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, _ 
            1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, _
            1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223] 
    
    ; Use static table of primes to start with
    For $p = 1 To $avPrimes[0]
        While 1
            $iTest = Mod($iWorking, $avPrimes[$p])
            If $iTest = 0 Then
                ; This is a factor
                $avRET[0] += 1
                $avRET[$avRET[0]] = $avPrimes[$p]
                $iWorking = $iWorking / $avPrimes[$p]
                If $iWorking = 1 Then
                    ; Last factor found
                    ExitLoop 2
                Else
                    ; Try same prime again
                    ContinueLoop
                EndIf
            Else
                ; This is not a factor, next prime
                ExitLoop
            EndIf
        WEnd
    Next

    ; Continue if remaining factors are larger than the static primes
    If $iWorking > $avPrimes[$avPrimes[0]] Then
        $iOddNum = $avPrimes[$avPrimes[0]] + 2
        While 1
            While 1
                $iTest = Mod($iWorking, $iOddNum)
                If $iTest = 0 Then
                    ; This is a factor
                    $avRET[0] += 1
                    $avRET[$avRET[0]] = $iOddNum
                    $iWorking = $iWorking / $iOddNum
                    If $iWorking = 1 Then
                        ; Last factor found
                        ExitLoop 2
                    Else
                        ; Try same odd number again
                        ContinueLoop
                    EndIf
                Else
                    ; This not a factor, next odd number
                    ExitLoop
                EndIf
            WEnd
            $iOddNum += 2
            If $iOddNum > Int(Sqrt($i)) Then
                ; Remaining number is prime = last factor
                $avRET[0] += 1
                $avRET[$avRET[0]] = $iWorking
                ExitLoop
            EndIf
        WEnd
    EndIf
    
    ; Resize the array and return
    ReDim $avRET[$avRET[0] + 1]
    Return $avRET
    
EndFunc   ;==>_Factor

The returned array may not be considered standard because for any valid input (a non-zero integer) it will have 1 or -1 as the first factor. The number 1 is not usually listed as a factor, but that seemed the most consistent way to handle negative numbers as inputs. Also, if $avReturn[0] = 2 then the input number was prime, making it a fair test for primality.

I'm looking into the more "non-naïve" methods for primality testing for future improvements.

:)

oks o ive posted my code!... its not very good scripting tho.. very noobish

Thank

Share this post


Link to post
Share on other sites

#3 ·  Posted (edited)

I wanted a function to return all factors of an integer, which involves primality testing. Wikipedia search turned up techniques way over my head (not surprising), but their "Naïve methods" gave me this as a start:

#include <array.au3>

While 1
    $n = InputBox("Factorizor", "Input number to factor: ")
    If @error Then Exit
    $n = Number($n)
    $iTimer = TimerInit()
    $avRET = _Factor($n)
    $ErrSav = @error
    $ExtSav = @extended
    $iTimer = TimerDiff($iTimer)
    _ArrayDisplay($avRET, "Primes of " & $n & ", @error = " & $ErrSav & ", @extended = " & $ExtSav & ", " & Round($iTimer / 1000, 3) & "sec")
WEnd

; ----------------------------------------------------------------------
; Function:         _Factor()
; Purpose:          Return all factors of a signed integer
; Syntax:           _Factor($i)
;   Where:          $i = signed integer value
; Returns:          A 1D array with [0] = count of factors
;   On success:     [1] = 1 or -1 depending on sign of input $i, [2] thru [n] = prime factors
;                   If [0] = 2 (because the only factors are 1 or -1 and the number) then input was prime.
;   On failure:     [0] = 0 and sets @error
; Notes:            Based on the simplest "naive" prime number test, sped up some by inclusion 
;                   of a short prime number table.
;                   The number 1 is not normally given as a prime factor, but is included so 
;                   the function can handle signed/unsigned numbers in a predictable manner.
;                   Element [1] of the array will be 1 or -1 depending on the sign of the input.
;                   Returns @error for non-integer or 0 inputs.
; Author:           PsaltyDS at www.autoitscript.com/forum
; Version: 1.0.0 dated 28 December, 2007
; ----------------------------------------------------------------------
Func _Factor($i)
    Local $avRET[1] = [0]
    Local $iTest, $iWorking, $iOddNum
    
    ; Test for valid input
    If IsInt($i) = 0 Then
        SetError(1)
        Return $avRET
    ElseIf $i = 0 Then
        SetError(2)
        Return $avRET
    EndIf
    
    ; Check for negative number
    Local $avRET[1024] = [1, 1]
    If $i < 0 Then
        $avRET[1] = -1
        $i = $i * - 1
    EndIf
    $iWorking = $i
    
    ; Quick return for input = 1
    If $iWorking = 1 Then
        ReDim $avRET[2]
        Return $avRET
    EndIf
    
    ; Initial table of primes
    Local $avPrimes[201] = [200, _
            2, 3, 5, 7, 11, 13, 17, 19, 23, 29, _
            31, 37, 41, 43, 47, 53, 59, 61, 67, 71, _
            73, 79, 83, 89, 97, 101, 103, 107, 109, 113, _
            127, 131, 137, 139, 149, 151, 157, 163, 167, 173, _
            179, 181, 191, 193, 197, 199, 211, 223, 227, 229, _
            233, 239, 241, 251, 257, 263, 269, 271, 277, 281, _
            283, 293, 307, 311, 313, 317, 331, 337, 347, 349, _
            353, 359, 367, 373, 379, 383, 389, 397, 401, 409, _
            419, 421, 431, 433, 439, 443, 449, 457, 461, 463, _
            467, 479, 487, 491, 499, 503, 509, 521, 523, 541, _
            547, 557, 563, 569, 571, 577, 587, 593, 599, 601, _
            607, 613, 617, 619, 631, 641, 643, 647, 653, 659, _ 
            661, 673, 677, 683, 691, 701, 709, 719, 727, 733, _
            739, 743, 751, 757, 761, 769, 773, 787, 797, 809, _ 
            811, 821, 823, 827, 829, 839, 853, 857, 859, 863, _ 
            877, 881, 883, 887, 907, 911, 919, 929, 937, 941, _ 
            947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, _ 
            1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, _ 
            1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, _
            1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223] 
    
    ; Use static table of primes to start with
    For $p = 1 To $avPrimes[0]
        While 1
            $iTest = Mod($iWorking, $avPrimes[$p])
            If $iTest = 0 Then
                ; This is a factor
                $avRET[0] += 1
                $avRET[$avRET[0]] = $avPrimes[$p]
                $iWorking = $iWorking / $avPrimes[$p]
                If $iWorking = 1 Then
                    ; Last factor found
                    ExitLoop 2
                Else
                    ; Try same prime again
                    ContinueLoop
                EndIf
            Else
                ; This is not a factor, next prime
                ExitLoop
            EndIf
        WEnd
    Next

    ; Continue if remaining factors are larger than the static primes
    If $iWorking > $avPrimes[$avPrimes[0]] Then
        $iOddNum = $avPrimes[$avPrimes[0]] + 2
        While 1
            While 1
                $iTest = Mod($iWorking, $iOddNum)
                If $iTest = 0 Then
                    ; This is a factor
                    $avRET[0] += 1
                    $avRET[$avRET[0]] = $iOddNum
                    $iWorking = $iWorking / $iOddNum
                    If $iWorking = 1 Then
                        ; Last factor found
                        ExitLoop 2
                    Else
                        ; Try same odd number again
                        ContinueLoop
                    EndIf
                Else
                    ; This not a factor, next odd number
                    ExitLoop
                EndIf
            WEnd
            $iOddNum += 2
            If $iOddNum > Int(Sqrt($i)) Then
                ; Remaining number is prime = last factor
                $avRET[0] += 1
                $avRET[$avRET[0]] = $iWorking
                ExitLoop
            EndIf
        WEnd
    EndIf
    
    ; Resize the array and return
    ReDim $avRET[$avRET[0] + 1]
    Return $avRET
    
EndFunc   ;==>_Factor

The returned array may not be considered standard because for any valid input (a non-zero integer) it will have 1 or -1 as the first factor. The number 1 is not usually listed as a factor, but that seemed the most consistent way to handle negative numbers as inputs. Also, if $avReturn[0] = 2 then the input number was prime, making it a fair test for primality.

I'm looking into the more "non-naïve" methods for primality testing for future improvements.

:)

It looks like you search through all 200 primes in the array but Nutster pointed out in a post recently that there is no need to go beyond Int($i^0.5). This could save some time for numbers smaller than 1223 ^ 2.

EDIT: Sorry, I should have said "Nutster is going to point out in the next post" but my crystal ball was playing up again.

Edited by martin

Serial port communications UDF Includes functions for binary transmission and reception.printing UDF Useful for graphs, forms, labels, reports etc.Add User Call Tips to SciTE for functions in UDFs not included with AutoIt and for your own scripts.Functions with parameters in OnEvent mode and for Hot Keys One function replaces GuiSetOnEvent, GuiCtrlSetOnEvent and HotKeySet.UDF IsConnected2 for notification of status of connected state of many urls or IPs, without slowing the script.

Share this post


Link to post
Share on other sites

#4 ·  Posted (edited)

Are you wanting to return all a number's prime factors or all factors of a number? You need separate functions to do each of these. See attached.

You do not need to check for prime factors larger than the square root of the number because there would be a number if multiplies by less than the square root. For example, examine 24. Square root is just under 5, which rounds down to 4. Let's see: 1 × 24 = 24, 2 × 12 = 24, 3 × 8 = 24, 4 × 6 = 24. After 4, the only factors are the ones you have already identified. Notice that with the exception of squares, like 6 × 6 = 36, one of the factors is less than the square root and one is more. So, if you are testing if you have a prime number, you only have to check up to the square root; if you have no factors before that, you have a prime number.

A note about the speed here. Yes, my Factor_Prime function could be faster by loading a number of primes into an array and comparing them, but I feel that my method here is:

  • Pretty easy to understand
  • Pretty quick to write and test
  • A little more versatile because it can handle much larger numbers.
If you are not going to be calling this multiple times, then building the Sieve or other prime number list is usually not worth it.

Edit: Add more detail

Factors.au3

Edited by Nutster

David Nuttall
Nuttall Computer Consulting

An Aquarius born during the Age of Aquarius

AutoIt allows me to re-invent the wheel so much faster.

I'm off to write a wizard, a wonderful wizard of odd...

Share this post


Link to post
Share on other sites

Yeh, just to add to Nutster's post...

In the factoring functions you have to decide what is more important to you, cpu time or memory. This is a reoccurring concept in programming. On one hand you could maintain either a list or repository of primes and thus do a quick comparison. This is advantageous since you would only have to calculate things once and you retain that knowledge. This would require a certain amount of memory though. On the other hand you can just use a simple sieve that starts a priori. This will require much more computation time and will essentially recompute everything, every time it is run. This will require little memory though. These two implementations clearly show how an algorithm should be tailored for the use to which it is put. The correct balance between memoization and an a priori algorithm must be made for every particular circumstance.

Just my own 2 cents...


Share this post


Link to post
Share on other sites

It looks like you search through all 200 primes in the array but Nutster pointed out in a post recently that there is no need to go beyond Int($i^0.5). This could save some time for numbers smaller than 1223 ^ 2.

EDIT: Sorry, I should have said "Nutster is going to point out in the next post" but my crystal ball was playing up again.

Look at the conditional exits in that loop. It doesn't go any deeper than necessary, and the entire list is only used if the number is larger than 1223^2.

:)


Valuater's AutoIt 1-2-3, Class... Is now in Session!For those who want somebody to write the script for them: RentACoder"Any technology distinguishable from magic is insufficiently advanced." -- Geek's corollary to Clarke's law

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0