PsaltyDS Posted December 28, 2007 Share Posted December 28, 2007 (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:expandcollapse popup#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 ;==>_FactorThe 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 December 28, 2007 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 Link to comment Share on other sites More sharing options...
zxzxzx Posted December 29, 2007 Share Posted December 29, 2007 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: expandcollapse popup#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 noobishThank Link to comment Share on other sites More sharing options...
martin Posted December 29, 2007 Share Posted December 29, 2007 (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: expandcollapse popup#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 January 2, 2008 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. Link to comment Share on other sites More sharing options...
Nutster Posted December 31, 2007 Share Posted December 31, 2007 (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 understandPretty quick to write and testA 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 detailFactors.au3 Edited December 31, 2007 by Nutster David NuttallNuttall 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... Link to comment Share on other sites More sharing options...
Wus Posted December 31, 2007 Share Posted December 31, 2007 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... Link to comment Share on other sites More sharing options...
PsaltyDS Posted January 5, 2008 Author Share Posted January 5, 2008 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 Link to comment Share on other sites More sharing options...
Recommended Posts
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 accountSign in
Already have an account? Sign in here.
Sign In Now