Primzahlen

1. offizieller Beitrag

    Hier mal ein kleines Skript zum Berechnen der Primzahlen bis 1000:

    [autoit]

    For $n = 2 To 100 Step 1
    $prime = 0
    For $x = 2 To Ceiling($n/0.5) Step 1
    If $x > 2 And Mod($x, 2) = 0 Then
    Else
    If Mod($n, $x) == 0 And ($n/$x > 1) Then
    ConsoleWrite($n & ' equals ' & $x & ' * ' & $n/$x & @CRLF)
    $prime = 1
    ExitLoop
    EndIf
    EndIf
    Next
    If $n > 1 And $prime = 0 Then
    ConsoleWrite($n & ' is a prime number' & @CRLF)
    EndIf
    Next

    [/autoit]


    Wenn man den Kommentar in Zeile 7 entfernt, erhält man gleich die Information, weshalb die andern Zahlen keine Primzahlen sind.

    Ich weis, das ist nichts neues, oder aufregendes (, oder gutes), aber mir war langweilig. :D

    MfG, James C.

    Danke, hier Version 2:

    [autoit]

    #NoTrayIcon

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

    GUICreate('autoit.de Primzahlen-Generator von James', 400, 300)
    $ListView = GUICtrlCreateListView('Zahl |Status ', 20, 20, 360, 220)
    $gVon = GUICtrlCreateInput(2, 20, 260, 50, 20, 0x2000)
    $gBis = GUICtrlCreateInput(100, 80, 260, 100, 20, 0x2000)
    $gAlle = GUICtrlCreateCheckbox('Alle Zahlen anzeigen', 190, 260, 120, 20)
    $Start = GUICtrlCreateButton('Start', 320, 260, 60, 20)
    GUISetState(@SW_SHOW)

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

    Do
    $Msg = GUIGetMsg()
    If $Msg = $Start Then
    $Von = GUICtrlRead($gVon)
    $Bis = GUICtrlRead($gBis)
    $Alle = GUICtrlRead($gAlle)
    GUICtrlDelete($ListView)
    $ListView = GUICtrlCreateListView('Zahl |Status ', 20, 20, 360, 220)
    For $n = $Von To $Bis Step 1
    $prime = 0
    For $x = 2 To Ceiling($n^0.5) Step 1
    If $x > 2 And Mod($x, 2) = 0 Then
    Else
    If Mod($n, $x) == 0 And ($n/$x > 1) Then
    If $Alle = 1 Then
    GUICtrlCreateListViewItem($n & '|' & $x & ' * ' & $n/$x, $ListView)
    EndIf
    $prime = 1
    ExitLoop
    EndIf
    If GUIGetMsg() = -3 Then Exit
    EndIf
    Next
    If $n > 1 And $prime = 0 Then
    GUICtrlCreateListViewItem($n & '|Primzahl', $ListView)
    EndIf
    Next
    EndIf
    Until $Msg = -3

    [/autoit]

    Du könntest das ein wenig effizienter machen:
    - es kann keine gerade Zahl ausser 2 sein. ==> fast die hälfte muss nicht überprüfft werden.
    - die Produkte der bereits durchsuchten Zahlen können auch keine Primzahl mehr sein. (frag mich nicht, wie man das umsetzten soll^^)

    mehr kommt mir auch gerade nicht mehr in den sinn... :)

    Hallo James,

    ein sehr schönes, kurzes und elegantes Programm. Auch ich habe vor Jahren mal sowas programmiert, allerdings damals noch in Pascal.
    Kleiner Tipp: Du überprüfst in Deinem Programm eine Zahl n auf prim, indem Du sie durch alle ganzen Zahlen von 2 bis n/2 dividierst. Es reicht aber, wenn Du sie durch alle ganzen Zahlen bis zur Wurzel aus n dividierst. Denn: wenn n keine Primzahl ist, also a * b = n, dann muss entweder a oder b kleiner sein als die Wurzel aus n. Es können nicht beide Faktoren größer sein als Wurzel n, weil sonst a *b nicht n sein könnte, sondern größer als n wäre.
    Also kann man programmieren:

    Bei den Primzahlen bis 1000 macht sich das noch nicht bemerkbar, wenn aber die obere Berechnungsschranke mal 6- oder 7-stellig wird, dann spürt man einen deutllichen Geschwindigkeitsgewinn, denn es müssen ja wesentlich weniger Divisionen durchgeführt werden. Z.B. bei n = 10000 muss ich nur durch die Zahlen von 2 bis 100 dividieren, statt von 2 bis 5000...

    Gruß
    Luki

    Einmal editiert, zuletzt von Luki (2. September 2011 um 23:02)

    Das ist meine Version, so effizient wie möglich (glaube ich ^^)

    Spoiler anzeigen
    [autoit]

    $timer=TimerInit()
    $str=_Prim(1000000,1000000) ;das war ein test ^^
    $timer=TimerDiff($timer)

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

    MsgBox(0,$timer&" ms",$str)

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

    Func _Prim($von,$bis)
    Local $ausgabe
    If $von<3 Then
    $von=3
    $ausgabe="2"&@CRLF
    Else
    $ausgabe=""
    EndIf
    If Mod($von,2)=0 Then $von+=1
    Local $tempvon,$i,$x,$isprim
    For $i=$von To $bis Step 2
    $tempvon=Floor($i/2)
    If Mod($tempvon,2)=0 Then $tempvon-=1
    $isprim=True
    For $x=$tempvon To 3 Step -2
    If Mod($i,$x)=0 Then
    $isprim=False
    ExitLoop
    EndIf
    Next
    If $isprim Then $ausgabe&=$i&@CRLF
    Next
    Return $ausgabe
    EndFunc

    [/autoit]

    von 1 bis 1000 in ca. 100ms
    von 1 bis 100 in ca. 1,5ms
    von 1 bis 30 in ca. 0,3 ms

    Dein Skript zeigt auch die 1 an

    Die 1 ist keine Primzahl und das hier ist meine Lösung:

    [autoit]

    ConsoleWrite(_GetPrimes(1000) & @CRLF)

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

    Func _GetPrimes($To)
    Local $sPrimes = ""
    For $i = 2 To $To
    If _IsPrim($i) Then $sPrimes &= $i & " "
    Next
    Return $sPrimes
    EndFunc

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

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

    [/autoit]
    Zitat von BugFix

    Ein Bemühen der Forumssuche hätte dir den Wettbewerb dazu geliefert. Hier der Ergebnispost: [Beendet] µitLight März

    Zitat von James1337

    Ich weis, das ist nichts neues, oder aufregendes (, oder gutes), aber mir war langweilig. :D


    PenGuin: Das ist eigentlich so wie mein Skript, nur das es in Funktionen aufgeteilt wurde.

    MfG, James