PrimA - der Primzahlengenerator

1. offizieller Beitrag

    Hätte ich auch noch was anzubieten:

    Beispielscript
    [autoit]


    $Primzahlen = _Primzahlen(1,2067)
    If $Primzahlen <> 0 Then
    _ArrayDisplay($Primzahlen)
    Else
    MsgBox(0,"","Es ist ein Fehler beim Aufruf der Funktion aufgetreten")
    EndIf

    [/autoit] [autoit][/autoit] [autoit]

    ; Erzeugt Primzahlen von/bis
    Func _Primzahlen($von,$bis)
    Local $zahl = $von, $aPrim[1], $teiler
    $aPrim[0] = 0
    If $von = 0 Or $bis = 0 Or $von > $bis Then Return 0
    Do
    If $zahl = 1 Then
    $zahl += 1
    ContinueLoop
    EndIf
    If $zahl = 2 Then
    ReDim $aPrim[UBound($aPrim)+1]
    $aprim[0] = UBound($aPrim)-1
    $aPrim[UBound($aPrim)-1] = $zahl
    $zahl += 1
    ContinueLoop
    Else
    If Mod($zahl,2) <> 0 Then
    $teiler = Round(SQRT($aPrim[UBound($aPrim)-1]))
    If Mod($teiler,2) = 0 Then $teiler = $teiler - 1
    Do
    If Mod($zahl,$teiler) = 0 Then ExitLoop
    $teiler = $teiler - 2
    Until $teiler < 3
    If $teiler < 3 Then
    ReDim $aPrim[UBound($aPrim)+1]
    $aprim[0] = UBound($aPrim)-1
    $aPrim[UBound($aPrim)-1] = $zahl
    EndIf
    EndIf
    EndIf
    $zahl += 1
    Until $zahl > $bis
    Return $aPrim
    EndFunc

    [/autoit]

    Edit: kleiner Fehler...

    Zur Nutzung dieses Forum's, ist ein Übersetzer für folgende Begriffe unerlässlich:

    "On-Bort, weier, verscheiden, schädliges, Butten steyling, näckstet, Parr, Porblem, scripe, Kompletenz, harken, manuel zu extramieren, geckukt, würglich, excell, acces oder Compilevorgeng"

    Einmal editiert, zuletzt von Micha_he (20. Januar 2009 um 22:04)

    • Offizieller Beitrag

    Eine recht schnelle Routine ist diese hier:

    [autoit]


    $o = 100000

    [/autoit][autoit][/autoit][autoit]

    $file = FileOpen("prim.txt", 2)

    [/autoit][autoit][/autoit][autoit]

    For $i = 2 To $o Step 1
    If IsPrime($i) Then FileWrite($file, $i & @CRLF)
    Next
    FileClose($file)

    [/autoit][autoit][/autoit][autoit]

    Func IsPrime($iValue)
    $maxText = Sqrt($iValue)
    For $i = 2 To $maxText
    If Mod($iValue, $i) = 0 Then Return False
    Next
    Return True
    EndFunc ;==>IsPrime

    [/autoit]

    Wenn ich mich recht erinnere hat Bernd670 die geschrieben.

    Hi,

    Sieb des Eratosthenes:

    Spoiler anzeigen
    [autoit]

    #include <ButtonConstants.au3>
    #include <GUIConstantsEx.au3>
    #include <WindowsConstants.au3>

    [/autoit] [autoit][/autoit] [autoit]

    Global Const $max = 100001
    Global $string = ''
    Dim $prim[$max + 1]

    [/autoit] [autoit][/autoit] [autoit]

    For $i = 1 To $max - 1
    $prim[$i - 1] = False
    Next

    [/autoit] [autoit][/autoit] [autoit]

    For $i = 2 To $max / 2
    For $j = 2 To $max / $i
    $prim[$i * $j] = True
    Next
    Next

    [/autoit] [autoit][/autoit] [autoit]

    For $i = 2 To $max
    If Not $prim[$i] Then $string = $string & $i & ' ; '
    Next

    [/autoit] [autoit][/autoit] [autoit]

    _StringDisplay($string, -1, $WS_VSCROLL)

    [/autoit] [autoit][/autoit] [autoit]

    ;===============================================================================
    ; Author.........: Oscar (http://www.autoit.de)
    ;===============================================================================
    Func _StringDisplay($sText, $sTitle = 'StringDisplay', $sEditStyle = -1, $iWidth = 400, $iHeight = 300, $iLeft = -1, $iTop = -1)
    If Not IsDeclared('BS_DEFPUSHBUTTON') Then Local Const $BS_DEFPUSHBUTTON = 0x00000001
    If Not IsDeclared('GUI_EVENT_CLOSE') Then Local Const $GUI_EVENT_CLOSE = 0xFFFFFFFD
    If Not IsDeclared('WS_EX_COMPOSITED') Then Local Const $WS_EX_COMPOSITED = 0x02000000
    If Not IsDeclared('WS_MAXIMIZEBOX') Then Local Const $WS_MAXIMIZEBOX = 0x00010000
    If Not IsDeclared('WS_MINIMIZEBOX') Then Local Const $WS_MINIMIZEBOX = 0x00020000
    If Not IsDeclared('WS_SIZEBOX') Then Local Const $WS_SIZEBOX = 0x00040000
    Local $bEventMode = Opt('GUIOnEventMode', 0)
    Local $hGui = GUICreate($sTitle, $iWidth, $iHeight, $iLeft, $iTop, BitOR($WS_MINIMIZEBOX, $WS_MAXIMIZEBOX, $WS_SIZEBOX), $WS_EX_COMPOSITED)
    Local $hEdit = GUICtrlCreateEdit($sText, 5, 5, $iWidth - 10, $iHeight - 65, $sEditStyle)
    GUICtrlSetResizing(-1, 2 + 4 + 32 + 64)
    Local $hClose = GUICtrlCreateButton('Close', $iWidth / 2 - 25, $iHeight - 55, 50, 22, $BS_DEFPUSHBUTTON)
    GUICtrlSetResizing(-1, 64 + 256 + 512)
    ControlFocus($hGui, '', $hClose)
    GUISetState(@SW_SHOW, $hGui)
    While True
    Switch GUIGetMsg()
    Case $hClose, $GUI_EVENT_CLOSE
    ExitLoop
    EndSwitch
    WEnd
    ControlFocus($hGui, '', $hEdit)
    Local $sSelectedText = ControlCommand($hGui, '', $hEdit, 'GetSelected', '')
    If @error Then $sSelectedText = ''
    GUIDelete($hGui)
    Opt('GUIOnEventMode', $bEventMode)
    Return $sSelectedText
    EndFunc ;==>_StringDisplay

    [/autoit]

    /Edit: Updatet mit _StringDisplay (thx Oscar ;))

    2 Mal editiert, zuletzt von anno2008 (20. Januar 2009 um 23:50)

    • Offizieller Beitrag

    Ich habe mal einen Laufzeittest von Deinem ( anno2008 ) und von Bernd's Code gemacht:

    Spoiler anzeigen
    [autoit]


    ;===============================================================================
    $timer = TimerInit()
    $o = 100000
    $out = ''
    For $i = 2 To $o Step 1
    If IsPrime($i) Then $out &= $i & @CRLF
    Next
    $diff = TimerDiff($timer)
    _StringDisplay(Round($diff/1000, 3) & ' sek.' & @CRLF & $Out, 'Funktion von Bernd670')

    [/autoit] [autoit][/autoit] [autoit]

    Func IsPrime($iValue)
    $maxText = Sqrt($iValue)
    For $i = 2 To $maxText
    If Mod($iValue, $i) = 0 Then Return False
    Next
    Return True
    EndFunc ;==>IsPrime
    ;===============================================================================

    [/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

    ;===============================================================================
    $timer = TimerInit()
    Global Const $max = 100001
    Global $string = ''
    Dim $prim[$max + 1]

    [/autoit] [autoit][/autoit] [autoit]

    For $i = 1 To $max - 1
    $prim[$i - 1] = False
    Next

    [/autoit] [autoit][/autoit] [autoit]

    For $i = 2 To $max / 2
    For $j = 2 To $max / $i
    $prim[$i * $j] = True
    Next
    Next

    [/autoit] [autoit][/autoit] [autoit]

    For $i = 2 To $max
    If Not $prim[$i] Then $string &= $i & @CRLF
    Next
    $diff = TimerDiff($timer)
    _StringDisplay(Round($diff/1000, 3) & ' sek.' & @CRLF & $string, 'Funktion von Anno2008')
    ;===============================================================================

    [/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

    ;===============================================================================
    Func _StringDisplay($sText, $sTitle = 'StringDisplay', $sEditStyle = -1, $iWidth = 400, $iHeight = 300, $iLeft = -1, $iTop = -1)
    If Not IsDeclared('BS_DEFPUSHBUTTON') Then Local Const $BS_DEFPUSHBUTTON = 0x00000001
    If Not IsDeclared('GUI_EVENT_CLOSE') Then Local Const $GUI_EVENT_CLOSE = 0xFFFFFFFD
    If Not IsDeclared('WS_EX_COMPOSITED') Then Local Const $WS_EX_COMPOSITED = 0x02000000
    If Not IsDeclared('WS_MAXIMIZEBOX') Then Local Const $WS_MAXIMIZEBOX = 0x00010000
    If Not IsDeclared('WS_MINIMIZEBOX') Then Local Const $WS_MINIMIZEBOX = 0x00020000
    If Not IsDeclared('WS_SIZEBOX') Then Local Const $WS_SIZEBOX = 0x00040000
    Local $iEventMode = Opt('GUIOnEventMode', 0)
    Local $hGui = GUICreate($sTitle, $iWidth, $iHeight, $iLeft, $iTop, BitOR($WS_MINIMIZEBOX, $WS_MAXIMIZEBOX, $WS_SIZEBOX), $WS_EX_COMPOSITED)
    Local $hEdit = GUICtrlCreateEdit($sText, 5, 5, $iWidth - 10, $iHeight - 65, $sEditStyle)
    GUICtrlSetResizing(-1, 2 + 4 + 32 + 64)
    Local $hClose = GUICtrlCreateButton('Close', $iWidth / 2 - 25, $iHeight - 55, 50, 22, $BS_DEFPUSHBUTTON)
    GUICtrlSetResizing(-1, 64 + 256 + 512)
    ControlFocus($hGui, '', $hClose)
    GUISetState(@SW_SHOW, $hGui)
    While True
    Switch GUIGetMsg()
    Case $hClose, $GUI_EVENT_CLOSE
    ExitLoop
    EndSwitch
    WEnd
    ControlFocus($hGui, '', $hEdit)
    Local $sSelectedText = ControlCommand($hGui, '', $hEdit, 'GetSelected', '')
    If @error Then $sSelectedText = ''
    GUIDelete($hGui)
    Opt('GUIOnEventMode', $iEventMode)
    Return $sSelectedText
    EndFunc ;==>_StringDisplay

    [/autoit]

    Deine Funktion ist fast 4 mal so schnell. Nicht schlecht! :thumbup:
    Habe ich mir mal archiviert...


    Es gibt aber einen wesentlichen Unterschied:
    Während das Sieb des Eratosthenes nur alle Primzahlen ausgibt und logischerweise schneller ist, kann bernds Code auch eine spezielle Zahl auf Primzahligkeit überprüfen.

    Twitter: @L3viathan2142
    Benutze AutoIt persönlich nicht mehr, da ich keinen Windows-Rechner mehr besitze.

    und da kommt wieder BugFix ins Spiel ... wer hat die schnellste Funktion zum Prüfen :P

    Zitat

    Laughing Man

    "I thought, what I'd do was, I'd pretend I was one of those deaf-mutes"

    • Offizieller Beitrag

    Du kannst nochmals gewaltig beschleunigen, wenn du meine Funktion zum Primzahlcheck verwendest.
    Meine Funktion dient ursprünglich zur Primfaktorzerlegung - aber bei nur einem Primfaktor als Ergebnis ist dies somit automatisch auch eine Primzahl.
    Hier mal beide Funktionen im Vergleichstest:

    Spoiler anzeigen
    [autoit]

    Local $zahl, $start, $time, $sumFunc1 = 0, $sumFunc2 = 0
    For $i = 1 To 200
    ConsoleWrite($i & @TAB)
    $zahl = Random(10, 100000000, 1)
    ConsoleWrite($zahl & @CRLF)
    $start = TimerInit()
    ConsoleWrite('_primzahlcheck:' & @TAB & @TAB & _primzahlcheck($zahl) & @TAB)
    $time = TimerDiff($start)
    ConsoleWrite($time & @CRLF)
    $sumFunc1 += $time
    $start = TimerInit()
    ConsoleWrite('_GetPrimeFactors:' & @TAB & _GetPrimeFactors($zahl, True) & @TAB )
    $time = TimerDiff($start)
    ConsoleWrite($time & @CRLF)
    $sumFunc2 += $time
    Next
    ConsoleWrite(@CRLF & 'Durchscnitt Func _primzahlcheck:' & @TAB & $sumFunc1/200 & @CRLF)
    ConsoleWrite('Durchscnitt Func _GetPrimeFactors:' & @TAB & $sumFunc2/200 & @CRLF)

    [/autoit] [autoit][/autoit] [autoit]

    Func _primzahlcheck($input_zahl)
    $teiler = 2
    $return = True
    While $teiler <= Sqrt($input_zahl)
    $rest = Mod($input_zahl,$teiler)
    If $rest = 0 Then
    $return = False
    EndIf
    $teiler = $teiler + 1
    WEnd
    Return $return
    EndFunc

    [/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

    Func _GetPrimeFactors($n, $bPrime=False)
    Local $F = ObjCreate("System.Collections.ArrayList")
    While Mod($n,2) == 0
    If $bPrime Then Return False
    $F.add(2)
    $n = $n/2
    WEnd
    While Mod($n,3) == 0
    If $bPrime Then Return False
    $F.add(3)
    $n = $n/3
    WEnd
    Local $t = 5
    Local $diff = 2
    While $t*$t <= $n
    While Mod($n,$t) == 0
    If $bPrime Then Return False
    $F.add($t)
    $n = $n/$t
    WEnd
    $t = $t + $diff
    $diff = 6 - $diff
    WEnd
    If $n > 1 Then $F.add($n)
    If $bPrime Then
    If $F.Count > 1 Then
    Return False
    Else
    Return True
    EndIf
    EndIf
    Local $out = ''
    For $element In $F
    $out &= $element & ','
    Next
    Return StringTrimRight($out, 1)
    EndFunc

    [/autoit]


    Und das sind die Ergebnisse, meine Funktion ist im Durchschnitt 28-mal schneller als die von dir verwendete ;) :

    Spoiler anzeigen
    • Offizieller Beitrag

    Hallo,

    IsPrime ist denoch schneller!

    Quellcode
    [autoit]

    Local $zahl, $start, $time, $sumFunc1 = 0, $sumFunc2 = 0, $sumFunc3 = 0
    For $i = 1 To 200
    ConsoleWrite($i & @TAB)
    $zahl = Random(10, 100000000, 1)
    ConsoleWrite($zahl & @CRLF)
    $start = TimerInit()
    ConsoleWrite('_primzahlcheck:' & @TAB & @TAB & _primzahlcheck($zahl) & @TAB)
    $time = TimerDiff($start)
    ConsoleWrite($time & @CRLF)
    $sumFunc1 += $time
    $start = TimerInit()
    ConsoleWrite('_GetPrimeFactors:' & @TAB & _GetPrimeFactors($zahl, True) & @TAB )
    $time = TimerDiff($start)
    ConsoleWrite($time & @CRLF)
    $sumFunc2 += $time
    $start = TimerInit()
    ConsoleWrite('IsPrime:' & @TAB & @TAB & IsPrime($zahl) & @TAB)
    $time = TimerDiff($start)
    ConsoleWrite($time & @CRLF)
    $sumFunc3 += $time
    Next
    ConsoleWrite(@CRLF & 'Durchscnitt Func _primzahlcheck:' & @TAB & $sumFunc1/200 & @CRLF)
    ConsoleWrite('Durchscnitt Func _GetPrimeFactors:' & @TAB & $sumFunc2/200 & @CRLF)
    ConsoleWrite('Durchscnitt Func IsPrime:' & @TAB & @TAB & $sumFunc3/200 & @CRLF)

    [/autoit] [autoit][/autoit] [autoit]

    Func _primzahlcheck($input_zahl)
    $teiler = 2
    $return = True
    While $teiler <= Sqrt($input_zahl)
    $rest = Mod($input_zahl,$teiler)
    If $rest = 0 Then
    $return = False
    EndIf
    $teiler = $teiler + 1
    WEnd
    Return $return
    EndFunc

    [/autoit] [autoit][/autoit] [autoit]

    Func _GetPrimeFactors($n, $bPrime=False)
    Local $F = ObjCreate("System.Collections.ArrayList")
    While Mod($n,2) == 0
    If $bPrime Then Return False
    $F.add(2)
    $n = $n/2
    WEnd
    While Mod($n,3) == 0
    If $bPrime Then Return False
    $F.add(3)
    $n = $n/3
    WEnd
    Local $t = 5
    Local $diff = 2
    While $t*$t <= $n
    While Mod($n,$t) == 0
    If $bPrime Then Return False
    $F.add($t)
    $n = $n/$t
    WEnd
    $t = $t + $diff
    $diff = 6 - $diff
    WEnd
    If $n > 1 Then $F.add($n)
    If $bPrime Then
    If $F.Count > 1 Then
    Return False
    Else
    Return True
    EndIf
    EndIf
    Local $out = ''
    For $element In $F
    $out &= $element & ','
    Next
    Return StringTrimRight($out, 1)
    EndFunc

    [/autoit] [autoit][/autoit] [autoit]

    Func IsPrime($iValue)
    $maxTest = Sqrt($iValue)
    For $i = 2 To $maxTest
    If Mod($iValue, $i) = 0 Then Return False
    Next
    Return True
    EndFunc ;==>IsPrime

    [/autoit]
    Ergebnis

    Dann muss ich noch eine posten: Mit Fehler-Tests schneller als IsPrime ;)

    Spoiler anzeigen
    [autoit]

    Func IsPrime2($iValue)
    Switch IsNumber($iValue)
    Case False
    $iValue = Number($iValue)
    EndSwitch
    Switch True
    Case $iValue = 2
    Return True
    Case $iValue < 2 Or Mod($iValue,2) = 0 Or IsFloat($iValue)
    Return False
    EndSwitch
    $maxTest = Floor(Sqrt($iValue))
    For $i = 3 To $maxTest Step 2
    If Mod($iValue, $i) = 0 Then Return False
    Next
    Return True
    EndFunc ;==>IsPrime2

    [/autoit]