prime number's for fun script

[Wurschtbrot]

Well im pretty new to Prime numbers ......

i was having some fun making little script + optimize it

expandcollapse popup

HotKeySet("{end}", "Terminate")
HotKeySet("{ins}", "calc");Shift-Alt-r
$prim = 3
$primNR = 2
$ii = 0
ConsoleWrite(@HOUR & ':' & @MIN & ':' & @SEC & @CRLF)
calc()
While 1
    Sleep(350)
WEnd
Func calc()
    While 1
        $i = 0
        $tmp = 0
        Do
            $i += 1
            If IsInt($prim / $i) Then $tmp += 1
        Until $tmp = 2
        If $i = $prim Then
            $primNR += 1
;~          ConsoleWrite('------------------------------' & @crlf);### Debug Console
;~          ConsoleWrite(' primNR = ' & $primNR & ' prim = ' & $prim & @CRLF);### Debug Console
;~          ConsoleWrite('------------------------------' & @crlf);### Debug Console
;~          Send("{" & $prim & " 1}")
;~          Send("{enter}")
;~ Else
;~      $ii += $i
;~      ConsoleWrite('Calc`s till now = ' & $ii & @CRLF);### Debug Console
        EndIf
        $prim += 2
        If $primNR = 3000 Then Terminate()
    WEnd

EndFunc  ;==>calc

Func Terminate()
    ConsoleWrite(@HOUR & ':' & @MIN & ':' & @SEC & @CRLF)
    Exit 0
EndFunc  ;==>Terminate

i only chek odd numbers this incresed speed significant and i want to add more to increase speed

since autoit isnt multi core programm i only get 25% cpu

>Running:(3.2.12.0):C:\Program Files\AutoIt3\autoit3.exe "C:\...\Primzahlen.au3"

06:15:30

06:17:15

+>06:17:15 AutoIT3.exe ended.rc:0

>Exit code: 0 Time: 106.468

i need help to optimize it a little more

Like "sum of digits" a number is dividable by 9 if her isint("sum of digits"/9)

in range of 1-50k it wont speed up the progress i guess but 50k - infinity(64bit variable=max ?^^ )

maybe we can reach a decent speed (i let it run until 5 mio+ already XD ) 4 fun

[PsaltyDS]

A related function: _Factor()

[enaiman]

Test this:

HotKeySet("{end}", "Terminate")
HotKeySet("{ins}", "calc");Shift-Alt-r
$primNR = 0
$i=0
ConsoleWrite(@HOUR & ':' & @MIN & ':' & @SEC & @CRLF)
calc()
While 1
    Sleep(350)
WEnd
Func calc()
    While 1
        $i += 1
        $j=2
        $not_prim = 0
        While $j <= $i/2    ;test only if it's smaller than half
            If Mod($i, $j) = 0 Then 
                $not_prim = 1
                ExitLoop
            EndIf
            If $j < 3 Then
                $j +=1
            Else
                $j +=2      
            EndIf
        WEnd
        If $not_prim = 1 Then 
            ContinueLoop
        Else
            ConsoleWrite($i & @CRLF)
            $primNR += 1
        EndIf
        If $primNR = 3000 Then Terminate()
    WEnd

EndFunc  ;==>calc

+>15:40:31 AutoIT3.exe ended.rc:0

>Exit code: 0 Time: 102.180

[enaiman]

It can be even better: 4.7 seconds for 3000 prime numbers:

HotKeySet("{end}", "Terminate")
HotKeySet("{ins}", "calc");Shift-Alt-r
$primNR = 0
$i=0
ConsoleWrite(@HOUR & ':' & @MIN & ':' & @SEC & @CRLF)
calc()
While 1
    Sleep(350)
WEnd
Func calc()
    While 1
        $i += 1
        $j=2
        $not_prim = 0
        Do 
            If Mod($i, $j) = 0 Then 
                $not_prim = 1
                ExitLoop
            EndIf
            If $j < 3 Then
                $j +=1
            Else
                $j +=2    
            EndIf
        Until $j > $i/$j    
        If $not_prim = 1 Then 
            ContinueLoop
        Else
            ConsoleWrite($i & @CRLF)
            $primNR += 1
        EndIf
        If $primNR = 3000 Then Terminate()
    WEnd

EndFunc  ;==>calc

I guess it might be faster than that ... I don't have too much time to refine the code ... heh ... weekend start

Edited May 30, 2008 by enaiman

[maroesjk]

Took me less than 1 second on a Pentium 4 @ 2.4 GHz (~ 0.90 seconds uncompiled and ~ 0.85 seconds compiled):

Global $SetStart = TimerInit(), $Primes[1], $Step = 1
For $TestNum = 1 to 3000 step $Step
    For $i = 1 to UBound($Primes) - 1
        If $Primes[$i] > .5 * $TestNum Then ExitLoop
        If Not Mod($TestNum, $Primes[$i]) Then ContinueLoop(2)
    Next
    If $TestNum = 1 Then ContinueLoop
    ReDim $Primes[UBound($Primes) + 1]
    $Primes[UBound($Primes) - 1] = $TestNum
    If $TestNum >= 3 Then $Step = 2
Next
MsgBox(64, 'Result', 'Found ' & UBound($Primes) - 1 & ' primes' & @CRLF & 'in ' & Round(TimerDiff($SetStart) / 1000, 3) & ' seconds')

[enaiman]

well ...

the idea was to find 3000 prime numbers (not prime numbers under 3000)

When your script runs in the the range 1-28000 (that's the range to find around 3000 prime numbers) it takes 48 seconds to find 3055 prime numbers.