Primzahlen automatisch ausgeben lassen

Übersicht BlitzBasic Allgemein

Neue Antwort erstellen

 

snörkl

Betreff: Primzahlen automatisch ausgeben lassen

 BeitragDo, Okt 25, 2007 19:17
Antworten mit Zitat
Benutzer-Profile anzeigen
Hi =) - heute hat unser Lehrer in Mathe erwähnt, dass man immer neue Primzahlen suchen würde um kompliziertere Verschlüsselungen verwenden zu können. Da kam mir die Idee, doch ein Programm zu schreiben, dass Primzahlen ausgibt.

Zum Programm:
In eine eingabefläche end eingeben um das Programm zu beenden, oder einfach aufs x drücken^^
Am Anfang gibt man die Zahl ein, bis zu der der Computer Primzahlen ausspucken soll^^
Sie werden dann berechnet und man kann mit den Pfeiltasten links und rechts durchscrollen (das ist leider ziemlich verbugt =( -> vielleicht kann jemand das Problem lösen und hier posten^^)
Nachdem man sie sich zu Gemüte geführt hat drückt man einfach Enter um auswählen zu können, ob man sie speichern möchte oder nicht (wenn ja, wird man nach einem namen gefragt, einfach sowas wie "primzahlen" eingeben und man erhält eine datei namens "primzahlen.txt" in den ordner, in dem der Generator gespeichert ist.).

Wie eben erwähnt, das scrollen ist verbugt, wenn jemand eine Lösung aufweisen kann, soll er sie doch bitte posten (man kann z.B. das x + 45 in ein x + (10*Len(i)) verändern, hat schon den ganz netten Effekt, das der Abstand auch bei hohen Zahlen immer gleich bleibt, aber das wichtigste wäre es eig. richtig zu scrollen^^ - d.h. auch das die zahlenreihe immer um genau ein "Feld weiterrückt" -)

Hier der Quellcode - jeder kann ihn verwenden, doch bitte ich darum, zu erwähnen, das er von mir stammt. DAnke =)

Code: [AUSKLAPPEN]
AppTitle "Primzahlenausgeber von M) - V. 1.0"

Global to_zahl$
Dim Primzahl(1)

Global zahl_geht = 1
Global x_pos = 0
Global y_pos = 0
Global x_verschiebung = 45

;//////////////////////////////HAUPTPROGRAMM\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

Repeat
   
   eingaben()

   teilen()

   zeichnen()
   
   speichern()
   
   WaitKey()

Forever

;///////////////////////////////FUNKTIONEN\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

Function eingaben()
   Cls
   
   Locate 0,0
   Print "irgendwo end eingeben zum beenden"
   to_zahl = Input("Zahl eingeben: ")
   If to_zahl = "end" Then End
   Dim Primzahl(to_zahl)
   
End Function
   
;--------------------------------------------------------------------------

Function teilen()
   
   For zahl = 2 To to_zahl
      
      zahl_ausgabe = zahl
      
      For x = 2 To 9
         If Not x = zahl Then
            If zahl Mod x = 0 Then zahl_geht = 0
         EndIf
      Next
      
      If zahl_geht = 1 Then Primzahl(zahl_ausgabe) = zahl
      zahl_geht = 1
   Next
   
End Function

;---------------------------------------------------------------------------

Function zeichnen()
   FlushKeys()
   Cls
   
   Locate 0,0
   Print "Pfeiltasten zum scrollen"
   Print "Mit enter verlassen"
   Print "(noch verbugt)"
   Delay 1300
   Cls
   
   ;Einmal zeichnen
   For i = 0 To to_zahl
      ;Zahl schreiben
      If primzahl(i) <> 0
         Text x_pos, y_pos, primzahl(i)
      
      ;Positionen
         y_pos = y_pos + 15
      EndIf
   
      If y_pos = 285
         x_pos = x_pos + 45         
         y_pos = 0
      EndIf
   Next
   
   ;------Verschieben-------
   
   ;Verschieben bei tastendruck -> und <-
   Repeat
   
      If KeyHit(205)
         Cls
         x_pos = 0
         ;verschiebung abziehen (richtung ->)
         x_pos = x_pos - x_verschiebung
         x_verschiebung = x_verschiebung + 45         
         For i = 0 To to_zahl
      
            ;Zahl schreiben
            If primzahl(i) <> 0
               Text x_pos, y_pos, primzahl(i)
            
            ;Positionen
               y_pos = y_pos + 15
            EndIf
         
            If y_pos = 285
               x_pos = x_pos + 45   
               y_pos = 0
            EndIf
         Next
      EndIf
      
      If KeyHit(203)
         Cls
         x_pos = 0
         ;verschiebung abziehen (richtung ->)
         x_pos = x_pos - x_verschiebung
         x_verschiebung = x_verschiebung + 45         
         For i = 0 To to_zahl
      
            ;Zahl schreiben
            If primzahl(i) <> 0
               Text x_pos, y_pos, primzahl(i)
            
            ;Positionen
               y_pos = y_pos + 15
            EndIf
         
            If y_pos = 285
               x_pos = x_pos + 45   
               y_pos = 0
            EndIf
         Next
      EndIf
   
   Until KeyHit(28)
   
End Function
   
;----------------------------------------------------------------------------

Function speichern()
   FlushKeys()
   Cls()
   
   Locate 0,0
   frage$ = Input("Möchten sie die Primzahlen speichern? (J/N) ")
   If frage = "end" Then End
   
   Select frage$
      Case "J"
         speichername$ = Input("Unter welchem Namen? (ohne Endung) ")
         datei$ = WriteFile (speichername + ".txt")
         For i = 0 To to_zahl
            If Primzahl(i) <> 0
               WriteLine datei, Primzahl(i)
            EndIf
         Next
         Print "Datei gespeichert! (Taste drücken)"
         
      Case "N"
         Print "Datei wird nicht gespeichert! (Taste drücken)"
         
      Default
         Print "Eingabe unbekannt. Datei wird nicht gespeichert!"
         Print "(Taste drücken)"
         
   End Select
   
End Function

DAK

 BeitragDo, Okt 25, 2007 21:37
Antworten mit Zitat
Benutzer-Profile anzeigen
recht nett, gabs aber schon öfters... das letzte mal unter: https://www.blitzforum.de/foru...t=primzahl

ich hab dir das ganze mal ein wenig entbuggt:
Code: [AUSKLAPPEN]
AppTitle "Primzahlenausgeber von M) - V. 1.0"

Global to_zahl$
Dim Primzahl(1)

Global zahl_geht = 1
Global x_pos = 0
Global y_pos = 0
Global x_verschiebung = 45

;//////////////////////////////HAUPTPROGRAMM\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

Repeat
   
   eingaben()

   teilen()

   zeichnen()
   
   speichern()
   
   WaitKey()

Forever

;///////////////////////////////FUNKTIONEN\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

Function eingaben()
   Cls
   
   Locate 0,0
   Print "irgendwo end eingeben zum beenden"
   to_zahl = Input("Zahl eingeben: ")
   If to_zahl = "end" Then End
   Dim Primzahl(to_zahl)
   
End Function
   
;--------------------------------------------------------------------------

Function teilen()
   
   For zahl = 2 To to_zahl
       
      zahl_ausgabe = zahl
       
      For x = 2 To 9
         If Not x = zahl Then
            If zahl Mod x = 0 Then zahl_geht = 0
         EndIf
      Next
       
      If zahl_geht = 1 Then Primzahl(zahl_ausgabe) = zahl
      zahl_geht = 1
   Next
   
End Function

;---------------------------------------------------------------------------

Function zeichnen()
   FlushKeys()
   Cls
   
   Locate 0,0
   Print "Pfeiltasten zum scrollen"
   Print "Mit enter verlassen"
   Print "(noch verbugt)"
   Delay 1300
   Cls
   
   ;Einmal zeichnen
   For i = 0 To to_zahl
      ;Zahl schreiben
      If primzahl(i) <> 0
         Text x_pos, y_pos, primzahl(i)
       
      ;Positionen
         y_pos = y_pos + 15
      EndIf
   
      If y_pos = 285
         x_pos = x_pos + 45         
         y_pos = 0
      EndIf
   Next
   
   ;------Verschieben-------
   
   ;Verschieben bei tastendruck -> und <-
   Repeat
   
      If KeyHit(205)
         Cls
         x_pos = 0
             y_pos = 0
         ;verschiebung abziehen (richtung ->)
         x_pos = x_pos - x_verschiebung
         x_verschiebung = x_verschiebung + 45         
         For i = 0 To to_zahl
            If y_pos = 285
               x_pos = x_pos + 45   
               y_pos = 0
            EndIf       
            ;Zahl schreiben
            If primzahl(i) <> 0
               Text x_pos, y_pos, primzahl(i)
             
            ;Positionen
               y_pos = y_pos + 15
            EndIf
         Next
      EndIf
       
      If KeyHit(203)
         Cls
         x_pos = 0
             y_pos = 0
         ;verschiebung abziehen (richtung ->)
         x_pos = x_pos - x_verschiebung
         x_verschiebung = x_verschiebung - 45         
         For i = 0 To to_zahl
            If y_pos = 285
               x_pos = x_pos + 45   
               y_pos = 0
            EndIf
            ;Zahl schreiben
            If primzahl(i) <> 0
               Text x_pos, y_pos, primzahl(i)
             
            ;Positionen
               y_pos = y_pos + 15
            EndIf
         Next
      EndIf
   
   Until KeyHit(28)
   
End Function
   
;----------------------------------------------------------------------------

Function speichern()
   FlushKeys()
   Cls()
   
   Locate 0,0
   frage$ = Lower(Input("Möchten sie die Primzahlen speichern? (J/N) "))
   If frage = "end" Then End
   
   Select frage$
      Case "j"
         speichername$ = Input("Unter welchem Namen? (ohne Endung) ")
         datei$ = WriteFile (speichername + ".txt")
         For i = 0 To to_zahl
            If Primzahl(i) <> 0
               WriteLine datei, Primzahl(i)
            EndIf
         Next
         Print "Datei gespeichert! (Taste drücken)"
         
      Case "n"
         Print "Datei wird nicht gespeichert! (Taste drücken)"
         
      Default
         Print "Eingabe unbekannt. Datei wird nicht gespeichert!"
         Print "(Taste drücken)"
         
   End Select
   
End Function


Noch ein paar Tipps um das ganze schneller zu machen:

Du brauchst um die Zahl x zu überprüfen nciht jede Zahl von 2-x überprüfen sondern nur jede Primzahl von 2-(x^0.5).
Ist bei bereichen von bis zu 100 oder so relaiv egal, aber wenn du dir alle Primzahlen bis zu einer Million ausgeben lassen willst, is es schon besser, wenns nicht ein halbes Jahr dafür braucht...

Außerdem brauchst du eine Zahl, die du als nicht-Primzahl identifiziert hast, nicht mehr weiter überprüfen (z.B. x = 12: zuerst wird herausgefunden, das es durch 2 dividerbar ist. Danach schauts aber weiter, obs noch durch was anderes teilber ist. Das ist zwar recht nett, aber unnötig)
Gewinner der 6. und der 68. BlitzCodeCompo
 

snörkl

 BeitragFr, Okt 26, 2007 16:51
Antworten mit Zitat
Benutzer-Profile anzeigen
Also bei mir läuft es mit for x = 2 to 9 viel schneller als mit for x = 2 to (to_zahl^0.5) ...
Du hast zwar eigentlich Recht damit, dass er nur 2,3,5,7,9 prüfen muss (weil 4 und 8 ja schon multiple von 2 sind), aber wenn er die Wurzel aus z.B. 10.000 zieht geht er noch viel weiter als bloss bis 9 -> das kann ich aber auch falsch verstanden haben, bin ja noch nicht in höheren klassen^^

das mit deiner idee aus der schleife auszusteigen ist gut, hab ich auch eingebaut =)

Vielen Dank für die Hilfe erstmal, schreib doch bitte zurück, weil ich meinen Code gerne optimieren würde

So, ich denke, ich habe es jetzt verstanden und meinen Code ziemlich stark umgeschrieben ^^
Das scrolling funktioniert dank Dir fast einwandfrei (muss nochmal gucken weil beim ersten keyhit 2 zeilen gescrollt werden, danach aber immer nur eine ...). An Tritons so schnellen code komme ich natürlich nicht heran, aber er schreibt mir die Primzahlen bis zur 1.000.000 in 3 sekunden -> am Anfang wäre eine Million gar nicht denkbar gewesen^^

Hier jetzt der (vorerst) letzte Code Code: [AUSKLAPPEN]
AppTitle "Primzahlenausgeber von M) - V. 2.1"

Global to_zahl$
Dim Primzahl(1)

Global zahl_geht = 1
Global x_pos = 0
Global y_pos = 0
Global x_verschiebung = 45

;//////////////////////////////HAUPTPROGRAMM\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

Repeat
   
   eingaben()

   teilen()

   zeichnen()
   
   speichern()
   
   WaitKey()

Forever

;///////////////////////////////FUNKTIONEN\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

Function eingaben()
   Cls
   
   Locate 0,0
   Print "irgendwo end eingeben zum beenden"
   to_zahl = Input("Zahl eingeben: ")
   If to_zahl = "end" Then End
   Dim Primzahl(to_zahl)
   
End Function
   
;--------------------------------------------------------------------------

Function teilen()
   wurzel = Sqr(to_zahl)
   For zahl = 3 To to_zahl
      If zahl Mod 2 = 0 Then zahl_geht = 0

      For x = 3 To wurzel Step 2
         If Not x = zahl Or zahl_geht = 0         
               If zahl Mod x = 0 Then zahl_geht = 0
         EndIf
      Next
      
      If zahl_geht = 1 Then Primzahl(zahl) = zahl
      If zahl_geht = 0 Then zahl_geht = 1

   Next           
End Function

;---------------------------------------------------------------------------

Function zeichnen()
   FlushKeys()
   Cls
   
   Locate 0,0
   Print "Pfeiltasten zum scrollen"
   Print "Mit enter verlassen"
   Delay 1300
   Cls
   
   ;Einmal zeichnen
   Text x_pos, y_pos, "2"
   y_pos = y_pos + 15
   
   For i = 0 To to_zahl
      ;Zahl schreiben
      If primzahl(i) <> 0
         Text x_pos, y_pos, primzahl(i)
      
      ;Positionen
         y_pos = y_pos + 15
      EndIf
   
      If y_pos = 285
         x_pos = x_pos + 45         
         y_pos = 0
      EndIf
   Next
   
   ;------Verschieben-------
   
   ;Verschieben bei tastendruck -> und <-
   Repeat
   
      If KeyHit(205)
         Cls
         x_pos = 0
         y_pos = 0
         
         ;verschiebung abziehen (richtung ->)
         x_verschiebung = x_verschiebung + 45
         x_pos = x_pos - x_verschiebung
         
         ;Die "2" zeichnen
         Text x_pos, y_pos, "2"
         y_pos = y_pos + 15
         
         For i = 0 To to_zahl
      
            ;Zahl schreiben
            If primzahl(i) <> 0
               Text x_pos, y_pos, primzahl(i)
            
            ;Positionen
               y_pos = y_pos + 15
            EndIf
         
            If y_pos = 285
               x_pos = x_pos + 45   
               y_pos = 0
            EndIf
         Next
      EndIf
      
      If KeyHit(203)
         Cls
         x_pos = 0
         y_pos = 0
         
         ;verschiebung abziehen (richtung ->)
         x_verschiebung = x_verschiebung - 45
         x_pos = x_pos - x_verschiebung   
         
         ;die "2" zeichnen
         Text x_pos, y_pos, "2"
         y_pos = y_pos + 15
               
         For i = 0 To to_zahl
      
            ;Zahl schreiben
            If primzahl(i) <> 0
               Text x_pos, y_pos, primzahl(i)
            
            ;Positionen
               y_pos = y_pos + 15
            EndIf
         
            If y_pos = 285
               x_pos = x_pos + 45   
               y_pos = 0
            EndIf
         Next
      EndIf
   
   Until KeyHit(28)
   
End Function
   
;----------------------------------------------------------------------------

Function speichern()
   FlushKeys()
   Cls()
   
   Locate 0,0
   frage$ = Input("Möchten sie die Primzahlen speichern? (j/n) ")
   If frage = "end" Then End
   
   Select frage$
      Case "j"
         speichername$ = Input("Unter welchem Namen? (ohne Endung) ")
         datei$ = WriteFile (speichername + ".txt")
         For i = 0 To to_zahl
            If Primzahl(i) <> 0
               WriteLine datei, Primzahl(i)
            EndIf
         Next
         Print "Datei gespeichert! (Taste drücken)"
         
      Case "n"
         Print "Datei wird nicht gespeichert! (Taste drücken)"
         
      Default
         Print "Eingabe unbekannt. Datei wird nicht gespeichert!"
         Print "(Taste drücken)"
         
   End Select
   
End Function


Danke für die Mithilfe, ich vermerke in einem Edit einfach wenn ich mein kleines scrollingproblem fertig gelöst habe^^

mfg,
Snörkl

DAK

 BeitragSa, Okt 27, 2007 0:05
Antworten mit Zitat
Benutzer-Profile anzeigen
Hab da mal was geschrieben, was du gut einbauen könntest, arbeitet ein wenig anders, als deins (wenn du 100 eingibst, suchts dir die ersten 100 Primzahlen) ist dafür aber ein ganzes stück schneller (verwendet das, was ich gemeint hab)
Code: [AUSKLAPPEN]
Dim Primzahl(1)

While Not KeyHit(1)
   prim(Input())
   i = 1
   While Primzahl(i)
      Print Primzahl(i)
      Delay 50
      i = i + 1
   Wend
Wend

Function prim(maxzahl)
   v = 2
   Dim Primzahl(maxzahl+1)
   Primzahl(1) = 2
   Primzahl(2) = 3
   For i = 4 To maxzahl
      If isprim(i) Then Primzahl(v)=i:v=v+1
   Next
End Function

Function isprim(zahl)
   x = 0
   w = zahl^.5
   Repeat
      x = x + 1
      test = Primzahl(x)
      If zahl Mod Primzahl(x) = 0 Then Return 0
   Until Primzahl(x) > w
   Return 1
End Function


Dann noch was zu dem Primzahlen anschauen nacher:
1. mach, das die Dinger, die gerade nicht am Schirm sind, nicht berechnet werden
2. mach bitte eine Seitenblätterfunktion (ist ein wenig mühsam, bei der Maximalzahl 1000000 bis ans Ende zu blättern...)
Gewinner der 6. und der 68. BlitzCodeCompo

Triton

 BeitragSa, Okt 27, 2007 19:46
Antworten mit Zitat
Benutzer-Profile anzeigen
Zitat:
Also bei mir läuft es mit for x = 2 to 9 viel schneller als mit for x = 2 to (to_zahl^0.5) ...

Verständlich, die Wurzel einer Zahl ist ja meist sehr viel größer als 9 Wink

Zitat:
Du hast zwar eigentlich Recht damit, dass er nur 2,3,5,7,9 prüfen muss (weil 4 und 8 ja schon multiple von 2 sind), aber wenn er die Wurzel aus z.B. 10.000 zieht geht er noch viel weiter als bloss bis 9 -> das kann ich aber auch falsch verstanden haben, bin ja noch nicht in höheren klassen^^

9 muss man auch nicht testen, da man das schon mit der 3 abgedeckt hat.

Offenbar hast du nicht richtig verstanden, was es mit Primzahlen auf sich hat,
oder warum man nur bis zur Wurzel der Zahl testen muss.

Die Wurzel einer Zahl ist in bezug auf ihre Teiler eine magische Grenze,
da es keine Zahl geben kann, die 3 oder mehr Teiler hat (sprich, eine nicht-Pz),
und wo der erste/kleinste Teiler nach der Wurzel auftritt.
Hat man also bis zur Wurzel keinen Teiler gefunden, gibts danach auch keinen mehr.


Soviel dazu.

Zum Programm kann ich nur anmerken, dass es uns nichts neues bringt und auch
das was es kann wurde schon besser/schneller umgesetzt.

Daher verschiebe ich es nach Allgemein, dann kann die Diskussion noch fortgeführt werden.
Coding: silizium-net.de | Portfolio: Triton.ch.vu
 

snörkl

 BeitragMo, Okt 29, 2007 17:53
Antworten mit Zitat
Benutzer-Profile anzeigen
thx @ triton, weil Du das topic nicht gleich zugemacht hast.
Ich habe das jetzt mit den Primzahlen verstanden, mein mathelehrer programmiert (warum programmieren wohl so viele mathelehrer Wink?^^) auch und ich hatte ihm das programm übers wochenende mal mitgegeben, er hatte dann (ich weiß nicht genau ob DAX das auch so meinte, ich schreibs einfach nochmal) den vorschlag das programm schneller zu machen, anhand des siebs von ^^ - namen vergessen - . Hatten wir mal in der grundschule aber ich habs natürlich schon längst vergessen lol. Also, das wichtigste an dem Sieb ist ja, dass man wenn man auf z.B. mod 2 prüft, er gleich alle multiplen von 2 mit löscht, bei 3 alle multiplen von 3. Dann muss er ja auf alle primzahlen bis zur wurzel der letzten zahl prüfen (->das hab ich jetzt endlich begriffen).

ich werde jetzt (wenn ich nicht weiter weiß mit hilfe von Dax's code) dieses "sieb" einbauen, werde es dann posten. Muss mir nur noch was überlegen, wie ich nur den sichtbaren bereich zeichne.

kann man eigentlich bei bb teile eines arrays löschen (also alle "nicht"-primzahlen gleich weglöschen - wie der delete-befehl bei types?)

Triton

 BeitragMo, Okt 29, 2007 18:44
Antworten mit Zitat
Benutzer-Profile anzeigen
Eratosthenes hieß der gute Mann. Und sein Sieb ist in der tat eine clevere
und etwas schnellere Variante um alle Pz bis zu einer Grenze zu finden.

Für größere Zahlen oder einzelne Zahlen ist es jedoch unbrauchbar.
Nicht zuletzt, weil man eine Liste mit den Zahlen anfertigen muss und da eben rausstreicht. Wenn man nicht ständig umsortiert, so wird diese Liste
viel Speicher verbrauchen, da auch eine gestrichene Zahl noch Platz belegt.


Sollte man z.B. mit dem Sieb die Zahl 2^61 - 1 testen, so wird dies wohl ne ganze Weile dauern.
Coding: silizium-net.de | Portfolio: Triton.ch.vu
 

snörkl

 BeitragDi, Okt 30, 2007 17:22
Antworten mit Zitat
Benutzer-Profile anzeigen
sry, ich habs nicht so mit griechischen Namen, obwohl ich das Fach Altgriechisch gewählt habe^^. Was würdest Du denn vorschlagen, was die schnellste Methode ist? (ich habe deinen Codearchiv-Eintrag gesehen, aber könntest Du vielleicht etwas Deine Herangehensweise erklären, damit ich meinem Lehrer - natürlich nicht als meine Idee - diese Methode erklären kann.)

vielen Dank für die Hilfe bis jetzt,
mfg,
Snörkl

Triton

 BeitragDi, Okt 30, 2007 20:45
Antworten mit Zitat
Benutzer-Profile anzeigen
Das Thema ist viel zu ausführlich, um es in einem kleinen Forenpost zu beschreiben. Jedenfalls gibt es viele andere Primzahltests, die meist ungleich schneller sind als Probedivision oder das Sieb des E.

Klick dich mal bei Wikipedia durch. Da findet man einiges.

Ich selbst habe mal einen eigenen Faktorisierungsalsogithmus entwickelt der bei speziellen Zahlen schneller wäre
als eine Probedivision. Darüber hinaus habe ich irgendwo im Codearchiv auch einen Primzahltest für Mersenne-Primzahlen (2^x - 1 = prim) hinterlassen.
Coding: silizium-net.de | Portfolio: Triton.ch.vu

Neue Antwort erstellen


Übersicht BlitzBasic Allgemein

Nach Oben

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group