# Prime Numbers

## Recommended Posts

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.

My projects:

##### Share on other sites

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.

This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

##### Share on other sites

Will using mod() speedup the process?

##### Share on other sites

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

This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

##### Share on other sites

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

```_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 by markyrocks

Spoiler

Â

##### Share on other sites

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.

My projects:

##### Share on other sites

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

Spoiler

Â

##### Share on other sites

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

##### Share on other sites

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.

Programming today is a race between software engineers striving to
build bigger and better idiot-proof programs, and the Universe
trying to produce bigger and better idiots.
So far, the Universe is winning.

##### Share on other sites

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

##### Share on other sites

Â

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

My projects:

##### Share on other sites

Â

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

##### Share on other sites

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.

This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

##### Share on other sites

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

##### Share on other sites

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

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

##### Share on other sites

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

##### Share on other sites

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.

##### Share on other sites

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

This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

##### Share on other sites

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.

Whenever someone says "pls" because it's shorter than "please", I say "no" because it's shorter than "yes".

##### Share on other sites

Side by side comparison:

```; 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)```

This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

## Create an account

Register a new account

• ### Recently Browsing   0 members

×

• Wiki

• Back

• #### Beta

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