Prime Numbers

[Rogue5099]

So I got bored did some research and played around with trying to check if and produce prime numbers.

This is what I have came up with so far but could I speed this process up?

Produce Prime Numbers:

$maxnumber = 300000
ConsoleWrite('Prime Numbers from 2 to ' & $maxnumber & @CRLF)
ConsoleWrite('2' & @CRLF)
$timer = TimerInit()
For $i = 1 To $maxnumber Step 2
    $x = Sqrt($i)
    If IsInt($x) = 0 Then
        $x = Floor($x)
        For $o = 2 To $x+1
            If IsInt($i/$o) Then
                $prime = 0
                ExitLoop
            Else
                $prime = 1
            EndIf
        Next
    Else
        $prime = 0
    EndIf
    If $prime = 1 Then ConsoleWrite($i & @CRLF)
Next
ConsoleWrite("Milliseconds Time: " & Int(TimerDiff($timer)) & @CRLF)

Check if number is Prime:

$number = 737373737373737
_CheckIfPrime($number)

Func _CheckIfPrime($number)
    $x = Sqrt($number)
    If IsInt($number/5) = 1 Then
        $prime = 0
    ElseIf IsInt($x) = 0 Then
        $x = Floor($x)
        For $o = 2 To $x+1
            If IsInt($number/$o) Then
                $prime = 0
                ExitLoop
            Else
                $prime = 1
            EndIf
        Next
    Else
        $prime = 0
    EndIf
    If $prime = 1 Then
        ConsoleWrite($number & " IS A PRIME NUMBER" & @CRLF)
    Else
        ConsoleWrite($number & " IS NOT A PRIME NUMBER" & @CRLF)
    EndIf
EndFunc

So far checking the number took about 80 seconds. Listing the numbers was 300,000 checked and listed at 37 seconds.

[jchd]

AutoIt strength clearly isn't computational speed, hence traditional primality or compositness tests aren't guaranteed to be any faster than trial divide. Also and since no efficient arbitrary-size integer arithmetic operation is built-in, the usefulness of AutoIt in number theory is irrevocably close to zero.

[michaelslamet]

Will using mod() speedup the process?

[jchd]

PowerMod would be the tool of choice, but it essentially requires arbitrary-length (or at least "large enough") integers in any practical implementation.

[markyrocks]

well I been playing around with this for shitz an giggles this is what i've come up with

expandcollapse popup

_CheckPrime()

Func _CheckPrime()
   $y = 0
   $max = 300000
   $number = 1
   dim $temp[100]
   
   while $number <> $max
   for $x = 1 to $number
   $remainder = Mod($number,$x)
   if $y >= UBound($temp) Then
      ReDim $temp[$y * 100]
      EndIf
   if $remainder = 0 Then
      $temp[$y] = $x
;~      MsgBox("","","temp " & $temp[$y] & "y " & $y)
      $y += 1
endif

    if $y >= 3 then
exitloop
endif
      EndIf
   Next
   if $temp[0] = $number or $temp[1] = $number Then
;~    MsgBox("","","number is prime" & $number)
      FileWrite("prime.txt",$number & @CRLF)
      $y = 0
   Else
      $y = 0
   EndIf
  
 $number += 1
;~ MsgBox("","",$number)
WEnd



EndFunc

I'd say this is considerably slower than your script lol its actually still running. But id definitely say this is a situation where processing power would make a difference.  I'm using a laptop that is a few years old and its using the cpu at 100%.  its been a few minutes and its only into like the 10000's lol but at least it works. i guess i can make it so that if $y > 3 then exitloop would prolly speed it up

Edited December 16, 2013 by markyrocks

[Rogue5099]

well I been playing around with this for shitz an giggles this is what i've come up with

I'd say this is considerably slower than your script lol its actually still running. But id definitely say this is a situation where processing power would make a difference.  I'm using a laptop that is a few years old and its using the cpu at 100%.  its been a few minutes and its only into like the 10000's lol but at least it works. i guess i can make it so that if $y > 3 then exitloop would prolly speed it up

 

Array's and ReDim would slow it up a bit and Array's do have a limit so I was trying to stay away from them,

Also while writing what I did I eliminated a lot of checks by (even numbers and being divisible by 5).  Also using the square root as the max number to divide by because once you go past the square root of the number you are just doing double checks.

[markyrocks]

the redim is redundant after i set it to exitloop after y>=3 still taking forever tho.  hence the $y will never be greater then ubound($temp).  I just wrote that as a learning exercise.  its been like 20 min and its still not past like 70000.  I think the point here is the Mod() isn't anyfaster.

Edited December 16, 2013 by markyrocks

[czardas]

This is taking about 20 seconds on my machine.

;

Local $number = 737373737373737
Local $bRet, $iTimer = TimerInit()

$bRet = _CheckIfPrime($number)
ConsoleWrite("Time taken = " & TimerDiff($iTimer) & @CRLF)

If $bRet Then
    ConsoleWrite($number & " IS A PRIME NUMBER" & @CRLF)
Else
    ConsoleWrite($number & " IS NOT A PRIME NUMBER" & @CRLF)
EndIf

Func _CheckIfPrime($number)
    If $number < 3 Then Return True
    
    Local $x = Sqrt($number)
    If Not Mod($number, 2) Or IsInt($x) Then Return False
    
    Local $bRet = True
    For $i = 3 To Floor($x) Step 2
        If Mod($number, $i) Then ContinueLoop
        $bRet = False
        ExitLoop
    Next
    Return $bRet
EndFunc

Edited December 16, 2013 by czardas

[funkey]

Here is an ASM code from Andy from German forum:

;Liste der Primzahlen bis $maximum
;32-Bit Bytecode by Andy, eine der ersten Versionen, daher unoptimiert und "langsam"

Local $maximum = 1299709 ;Obergrenze der Primzahlen
Local $file = "Prim_" & $maximum & ".au3" ;Datei, in welche die Primzahlen geschrieben werden

$t = TimerInit() ;Timestamp sichern
$tStruct = DllStructCreate("uint Limit;uint Limes;char Mem[" & $maximum + 10 & "]") ;char, dann kann man nachher schön mit den stringfunktionen suchen
;die folgenden 4 Zeilen sparen einige Zeilen Assemblercode, außerdem kann man sich den Speicherinhalt in AutoIt anschauen
DllStructSetData($tStruct, "Mem", "001") ;die ersten 3 Zahlen setzen, 0=0 1=0 2=1 , 2 ist die erste Primzahl
DllStructSetData($tStruct, "Limit", $maximum);limit in die Struct schreiben
DllStructSetData($tStruct, "Limes", Floor(Sqrt($maximum)) + 1);wurzel aus limit in die struct schreiben
$bytecode = "0x558B6C24088B5D00B803000000C74405083130313083C00439D876F189EF83C70889FE8B4D00BB0300000089D8F7E0C604063001D839C87CF683C3023B5D007737803C1E3175F2535189D8BB0A00000031C931D2F7F3665280C10109C075F366580C30AAE2F9C6070D83C701595B3B5D047CB83B5D007CC1C607005DC3"
$tCodeBuffer = DllStructCreate("byte[" & StringLen($bytecode) / 2 & "]") ;Speicher für den bytecode reservieren...
DllStructSetData($tCodeBuffer, 1, $bytecode);...und mit dem Bytecode beschreiben
;die folgende Zeile startet den bytecode im Speicher und kehrt danach hierher zurück
$t = TimerInit() ;Timestamp sichern
$a = DllCall("user32.dll", "int", "CallWindowProcW", "ptr", DllStructGetPtr($tCodeBuffer), "ptr", DllStructGetPtr($tStruct), "int", 0, "int", 0, "int", 0);bytecode aufrufen, rückgabe in a[0]

$primzahlen = "2" & @CR & "3" & @CR & DllStructGetData($tStruct, "Mem");2 und 3 sind die ersten Primzahlen, dann folgt der Rest
$m = TimerDiff($t) ;Zeit seit Programmstart

FileDelete($file) ;Primzahldatei löschen
FileWrite($file, $primzahlen) ;Ausgabe der Primzahlen in Datei
$m1 = TimerDiff($t);Zeit seit Programmstart incl Datei schreiben

StringReplace($primzahlen, @CR, @CR, 0, 1) ;alle CR im String zählen.....auch AutoIt hat SPEEEEED^^
$anzahlprim = @extended ;hätte man auch vom Assembler zurückgeben lassen können^^

MsgBox(262144, "Primzahlen bis " & $maximum, $anzahlprim & " Primzahlen ermittelt in " & Int($m) & " Millisekunden" & @CRLF & _
"Primzahlen ermitteln und in Datei schreiben in " & Int($m1) & " Millisekunden." & @CRLF & _
"Ausgabe der Zahlen folgt in die Datei " & $file & @CRLF & _
"Die Primzahldatei wird nun angezeigt...")
ShellExecute($file) ;in Scite anzeigen

It even writes the numbers to file in very little time.

[czardas]

This modification gives somewhere between 20% (if prime) and a potential 80% (if not prime) increase in speed to my previous example. The speed increase cannot be defined accurately.

:

Local $number = 737373737373737
Local $bRet, $iTimer = TimerInit()

$bRet = _CheckIfPrime($number)
ConsoleWrite("Time taken = " & TimerDiff($iTimer) & @CRLF)

If $bRet Then
    ConsoleWrite($number & " IS A PRIME NUMBER" & @CRLF)
Else
    ConsoleWrite($number & " IS NOT A PRIME NUMBER" & @CRLF)
EndIf

Func _CheckIfPrime($number)
    If $number < 3 Or $number = 5 Then Return True

    Local $x = Sqrt($number)
    If Not (Mod($number, 2) And Mod($number, 5)) Or IsInt($x) Then Return False

    Local $bRet = True
    For $j = 3 To 11 Step 2
        If $j = 5 Then ContinueLoop

        For $i = $j To Floor($x) Step 10
            If Mod($number, $i) Then ContinueLoop
            $bRet = False
            ExitLoop 2
        Next
    Next
    Return $bRet
EndFunc

;

I'm sure there are faster algorithms, but this is still interesting. It's pretty much pot luck if a factor is found quickly or not.

Generate the first 100,000 primes.

#include <Array.au3>

Local $sString = "1,2,3,", $number = 5, $iPrimeCount = 3, $iTimer = TimerInit()
Do
    If _CheckIfPrime($number) Then
        $sString &= $number & ","
        $iPrimeCount += 1
    EndIf
    $number += 2
Until $iPrimeCount = 100000

$sString = StringTrimRight($sString, 1)
Local $aPrimes = StringSplit($sString, ",")

ConsoleWrite("Time taken = " & TimerDiff($iTimer) & @CRLF)

_ArrayDisplay($aPrimes)

Func _CheckIfPrime($number)
    If $number < 3 Or $number = 5 Then Return True

    Local $x = Sqrt($number)
    If Not (Mod($number, 2) And Mod($number, 5)) Or IsInt($x) Then Return False

    Local $bRet = True
    For $j = 3 To 11 Step 2
        If $j = 5 Then ContinueLoop

        For $i = $j To Floor($x) Step 10
            If Mod($number, $i) Then ContinueLoop
            $bRet = False
            ExitLoop 2
        Next
    Next
    Return $bRet
EndFunc

Edited December 16, 2013 by czardas

[Rogue5099]

 

This modification gives somewhere between 20% (if prime) and a potential 80% (if not prime) increase in speed to my previous example. The speed increase cannot be defined accurately.

:

Local $number = 737373737373737
Local $bRet, $iTimer = TimerInit()

$bRet = _CheckIfPrime($number)
ConsoleWrite("Time taken = " & TimerDiff($iTimer) & @CRLF)

If $bRet Then
    ConsoleWrite($number & " IS A PRIME NUMBER" & @CRLF)
Else
    ConsoleWrite($number & " IS NOT A PRIME NUMBER" & @CRLF)
EndIf

Func _CheckIfPrime($number)
    If $number < 3 Or $number = 5 Then Return True

    Local $x = Sqrt($number)
    If Not (Mod($number, 2) And Mod($number, 5)) Or IsInt($x) Then Return False

    Local $bRet = True
    For $j = 3 To 11 Step 2
        If $j = 5 Then ContinueLoop

        For $i = $j To Floor($x) Step 10
            If Mod($number, $i) Then ContinueLoop
            $bRet = False
            ExitLoop 2
        Next
    Next
    Return $bRet
EndFunc

;

I'm sure there are faster algorithms, but this is still interesting. It's pretty much pot luck if a factor is found quickly or not.

Generate the first 100,000 primes.

#include <Array.au3>

Local $sString = "1,2,3,", $number = 5, $iPrimeCount = 3, $iTimer = TimerInit()
Do
    If _CheckIfPrime($number) Then
        $sString &= $number & ","
        $iPrimeCount += 1
    EndIf
    $number += 2
Until $iPrimeCount = 100000

$sString = StringTrimRight($sString, 1)
Local $aPrimes = StringSplit($sString, ",")

ConsoleWrite("Time taken = " & TimerDiff($iTimer) & @CRLF)

_ArrayDisplay($aPrimes)

Func _CheckIfPrime($number)
    If $number < 3 Or $number = 5 Then Return True

    Local $x = Sqrt($number)
    If Not (Mod($number, 2) And Mod($number, 5)) Or IsInt($x) Then Return False

    Local $bRet = True
    For $j = 3 To 11 Step 2
        If $j = 5 Then ContinueLoop

        For $i = $j To Floor($x) Step 10
            If Mod($number, $i) Then ContinueLoop
            $bRet = False
            ExitLoop 2
        Next
    Next
    Return $bRet
EndFunc

 

I like this style as well! Only thing I noticed was that you have 1 as a prime number which the first prime number is 2.  These 2 lines also exempt negative numbers and number 1.

If $number = 2 Or $number = 5 Then Return True

If $number < 0 Then Return False

[czardas]

 

I like this style as well! Only thing I noticed was that you have 1 as a prime number which the first prime number is 2.  These 2 lines also exempt negative numbers and number 1.

If $number = 2 Or $number = 5 Then Return True

If $number < 0 Then Return False

 

Thanks. I agree the code needs some tweaking for negative primes (using Abs) and error checks also need adding. It was the method that interested me the most. As far as the number 1 is concerned, I was a little surprised to see people excluding it from the list. I always interpreted a prime as being any whole number which only divides by 1 and itself. This is the definition we were taught in school, and this would mean the number 1 does qualify as a prime. I need to check my sources.

Zero definately needs removing though. If the code is useful to you, then tweak it any way you wish.

Edit

I'm getting somewhere researching this. The number one was originally considered a prime number, until they redefined the meaning of the word. I'm not exactly sure why they did this yet. It is entirely a question of semantics. It reminds me a bit of Pluto no longer being classified as a planet. Funny old world.

Edited December 17, 2013 by czardas

[jchd]

Divisibility by the unit is a triviality. Also if 1 is considered prime the fundamental theorem of arithmetic no longer holds: decomposition into primes is no longer unique. That would need rephrasing most results in number theory. It's therefore more natural to exclude 1 from PRIMES.

[czardas]

I understand the reasons for the change, as explained in the video. The redefinition makes things easier by not having to constantly exclude the unique exception to the rule - unity. it's nothing more than semantics, and has no deeper significance beyond the convenience factor - it doesn't really matter what you call it. Quite interesting though.

I would have said all primes greater than one are a subset of all primes greater than zero, rather than turning 2000+ years of established definition on its head.

Rewording the theory won't break anything. It's clearly too late to go down that path now though. The historians will have to struggle with it instead.

Apologies for all the edits in this post.

Edited December 17, 2013 by czardas

[lark]

 I'm surprised no one has mentioned prime sieves yet. Prime sieves work by filtering out non-primes, instead of checking whether each number is prime. The fastest sieve I've heard of is the sieve of atkin, which uses quadratics to determine prime numbers. Pseudo code on the wikipedia page is here: http://en.wikipedia.org/wiki/Sieve_of_Atkin

Another popular prime sieve is the sieve of eratosthenes- its much simpler, but not quite as fast.

Here is an implementation of the sieve of atkin in autoit:

expandcollapse popup

#include <Array.au3>

Func getPrimes($limit)
    Local $isPrime[$limit]
    Local $i, $x, $y, $n

    For $i = 0 To $limit-1
        $isPrime[$i] = False
    Next

    For $x = 1 To Sqrt($limit)
        For $y = 1 To Sqrt($limit)
            $n = 4*$x*$x  + $y*$y
            If ($n <= $limit) And (Mod($n, 12) == 1 Or Mod($n, 12) == 5) Then
                $isPrime[$n] = Not $isPrime[$n]
            EndIf

            $n = 3*$x*$x  + $y*$y
            If ($n <= $limit) And (Mod($n, 12) == 7) Then
                $isPrime[$n] = Not $isPrime[$n]
            EndIf

            $n = 3*$x*$x  - $y*$y
            If ($x > $y) And ($n <= $limit) And (Mod($n, 12) == 11) Then
                $isPrime[$n] = Not $isPrime[$n]
            EndIf
        Next
    Next

    For $n = 5 To Sqrt($limit)
        If $isPrime[$n] Then
            $i = 1
            $j = $i * $n * $n
            While $j < $limit
                $isPrime[$j] = False
                $i += 1
                $j = $i * $n * $n
            WEnd
        EndIf
    Next

    Local $size = 2

    For $i = 5 To UBound($isPrime)-1
        If $isPrime[$i] Then $size += 1
    Next

    Local $primes[$size]
    $primes[0] = 2
    $primes[1] = 3

    $i = 2
    $j = 0
    While $i < UBound($primes)
        If $isPrime[$j] Then
            $primes[$i] = $j
            $i += 1
        EndIf
        $j += 1
    WEnd

    Return $primes

EndFunc

Local $timer = TimerInit()
Local $primes = getPrimes(100000)
ConsoleWrite("Time taken: " & TimerDiff($timer) & @CRLF)

_ArrayDisplay($primes)

It took ~780 milliseconds to compute the first 100,000 primes on my computer, compared to ~45 seconds with the code above.

-earthlark

[czardas]

That looks good. I knew there were faster methods but I need to study the sieve methods to understand them. Thanks for posting this. Ah that pseudo code on wiki seems easy to read.

The prime number generation code I wrote above was really only to test the function for testing primes rather than specifically generate them. I imagine there will be some short cuts for that too which I don't know about. Your post has given me some new ideas already.

Edited December 17, 2013 by czardas

[czardas]

I just looked at this in a bit more depth. The code above only produces 9591 primes (not 100,000) so the timing comparison is out by quite a large factor. The AutoIt limitation of 16 million array elements imposes a restriction of primes up to 8 digits using the method as it is coded right now. It's a facinating algorithm though. I imagine it can be tweaked - needs some thought.

[jchd]

I can't believe Atkin's sieve might be faster than Erastosthenes', at least when comparing equally carefull implementations in a general-purpose language.

BTW, there are exactly 9592 primes ≤ 100000

[JohnQSmith]

The code above only produces 9591 primes

 

9592... the _ArrayDisplay starts counting at 0; classic off-by-one error.

100000th prime is 1299709, so replacing the getPrimes(100000) with getPrimes(1299710) runs in about 20.7 secs on my computer.

[jchd]

Side by side comparison:

expandcollapse popup

; prime list with sieves: Eratosthenes vs. Atkin
; builds a list of primes <= a given positive integer $N
; Eratosthesnes is much faster with a direct array, but using a bitfield (kind of) allows $N > 16 M

#include <Array.au3>

Global $N = 100000

    ; Setup the bitfield.
    ; In this "bitfield", we set bits to 1 when the
    ; corresponding integer is composite.
    ; The even prime is always a pain in the ass
    ; but here we take advantage of its unicity:
    ; we only work with odd numbers from now on.
    ; Every bit in the int32 populating the array
    ; flags an odd number, starting with 1.
    ; Hence we start testing at 3

Global $ndwords = Floor(($N + 31) / 32)
Global $dwords[$ndwords]
Global $primelist = "2"
Global $idx

Global $t = TimerInit()
For $test = 3 To $N Step 2
    $idx = (($test - 1) / 2) - 1
    If BitAND($dwords[Floor($idx / 32)], BitShift(1, -Mod($idx, 32))) = 0 Then
        $primelist &= "," & $test
        For $i = 3 * $test To $N Step 2 * $test
            $idx = (($i - 1) / 2) - 1
            $dwords[Floor($idx / 32)] = BitOR($dwords[Floor($idx / 32)], BitShift(1, -Mod($idx, 32)))
        Next
    EndIf
Next
ConsoleWrite("Bitfield Eratosthenes took: " & TimerDiff($t) & @LF)
Global $primes = StringSplit($primelist, ',', 2)
_ArrayDisplay($primes)


Global $prime[$N]
$primelist = "2"
$t = TimerInit()
For $test = 3 To $N Step 2
    If $prime[$test] = 0 Then
        $primelist &= "," & $test
        For $i = 3 * $test To $N Step 2 * $test
            $prime[$i] = 1
        Next
    EndIf
Next
ConsoleWrite("Array Eratosthenes took: " & TimerDiff($t) & @LF)
Global $primes = StringSplit($primelist, ',', 2)
_ArrayDisplay($primes)


;~ #include <Array.au3>

Func getPrimes($limit)
    Local $isPrime[$limit]
    Local $i, $x, $y, $n

    For $i = 0 To $limit-1
        $isPrime[$i] = False
    Next

    For $x = 1 To Sqrt($limit)
        For $y = 1 To Sqrt($limit)
            $n = 4*$x*$x  + $y*$y
            If ($n <= $limit) And (Mod($n, 12) == 1 Or Mod($n, 12) == 5) Then
                $isPrime[$n] = Not $isPrime[$n]
            EndIf

            $n = 3*$x*$x  + $y*$y
            If ($n <= $limit) And (Mod($n, 12) == 7) Then
                $isPrime[$n] = Not $isPrime[$n]
            EndIf

            $n = 3*$x*$x  - $y*$y
            If ($x > $y) And ($n <= $limit) And (Mod($n, 12) == 11) Then
                $isPrime[$n] = Not $isPrime[$n]
            EndIf
        Next
    Next

    For $n = 5 To Sqrt($limit)
        If $isPrime[$n] Then
            $i = 1
            $j = $i * $n * $n
            While $j < $limit
                $isPrime[$j] = False
                $i += 1
                $j = $i * $n * $n
            WEnd
        EndIf
    Next

    Local $size = 2

    For $i = 5 To UBound($isPrime)-1
        If $isPrime[$i] Then $size += 1
    Next

    Local $primes[$size]
    $primes[0] = 2
    $primes[1] = 3

    $i = 2
    $j = 0
    While $i < UBound($primes)
        If $isPrime[$j] Then
            $primes[$i] = $j
            $i += 1
        EndIf
        $j += 1
    WEnd

    Return $primes

EndFunc

Local $timer = TimerInit()
Local $primes = getPrimes($N)
ConsoleWrite("Atkin took: " & TimerDiff($timer) & @CRLF)

_ArrayDisplay($primes)