# Return all factors of an integer

## Recommended Posts

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 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 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.

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 on other sites

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 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 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

## 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

• ### Recently Browsing   0 members

×

• Wiki

• Back

• #### Beta

• Git
• FAQ
• Our Picks
×
• Create New...