Primzahlen ermitteln

Übersicht

BlitzBasic

Codearchiv

	Triton Betreff: Primzahlen ermitteln	So, Jun 05, 2005 15:45 Antworten mit Zitat
Da immer mal wieder Primzahlen zum Thema kommen und ich mich selbst seit einiger Zeit damit beschäftige, habe ich - natürlich - einen eigenen Primzahltest geschrieben. Dieses Programm ermittelt also Primzahlen und schreibt sie zu je 500.000 Stück in fortlaufend nummerierte Txt-Dateien. Es läuft relativ schnell, es gibt aber noch Optimierungspotenzial, indem man einfach jede bisher gefundene Primzahl als potenziellen Teiler überprüft. Ist eine Primzahl ein Teiler der Zahl die man untersuchen will, so ist die Zahl keine Primzahl. Die Grenze liegt bei 2^31, da hier die Zahlenbereichsbeschränkungen von BlitzBasic zum Tragen kommen. Wenn man das Programm unterbricht und dann weiterlaufen lassen will, muss man zudem den Wert von der Startzahl z und der txt-nummerierung ändern. BlitzBasic: [AUSKLAPPEN] [EINKLAPPEN] ; März 2005 ; by Triton ;** www.silizium-net.de Graphics 400,300,32,2 AppTitle(\"Primzahlen\") txt=1 DeleteFile(\"primzahlen\"+txt+\".txt\") dat=WriteFile(\"primzahlen\"+txt+\".txt\") CloseFile dat dat=OpenFile(\"primzahlen\"+txt+\".txt\") z=1 ;Startzahl (wer hoch beginnen möchte, nehme 1002888199) t1=MilliSecs() While Not KeyDown(1) zahl$ = Str(z) If primzahl(zahl$) = 1 Then WriteLine dat,zahl$ i=i+1 End If If i Mod 500 = 0 Then Print zahl$ If i=500000 Then t2=MilliSecs()-t1 min=t2/60000 sek=(t2 Mod 60000)/1000 If min=1 Then WriteLine dat,\"Benötigte Zeit: \"+min+\" Minute, \"+sek+\" Sekunden\" If min>1 Then WriteLine dat,\"Benötigte Zeit: \"+min+\" Minuten, \"+sek+\" Sekunden\" t1=MilliSecs() CloseFile dat dat=WriteFile(\"primzahlen\"+txt+\".txt\") txt=txt+1 i=0 End If z=z+2 Wend ;--- Function primzahl$(zahl$) If zahl$=1 Then Return 0 If zahl$=2 Or zahl$=3 Or zahl$=5 Then Return 1 If Right(zahl$,1) = 5 Then Return 0 For stelle=1 To Len(zahl$) ziffer$=Mid(zahl$,stelle,1) quersumme=quersumme+Int(ziffer$) Next If quersumme Mod 3 = 0 Then Return 0 ;schließt Zahl aus, wenn 3/9 = Teiler wz=Int(zahl$) For i=3 To Sqr(wz) Step 2 If wz Mod i = 0 Then Return 0 Next Return 1 End Function
Coding: silizium-net.de \| Portfolio: Triton.ch.vu

Triton

Betreff: Primzahlen ermitteln

So, Jun 05, 2005 15:45
Antworten mit Zitat

Da immer mal wieder Primzahlen zum Thema kommen und ich mich selbst seit einiger Zeit damit beschäftige, habe ich - natürlich - einen eigenen Primzahltest geschrieben.
Dieses Programm ermittelt also Primzahlen und schreibt sie zu je 500.000 Stück in fortlaufend nummerierte Txt-Dateien. Es läuft relativ schnell, es gibt aber noch Optimierungspotenzial, indem man einfach jede bisher gefundene Primzahl als potenziellen Teiler überprüft. Ist eine Primzahl ein Teiler der Zahl die man untersuchen will, so ist die Zahl keine Primzahl. Die Grenze liegt bei 2^31, da hier die Zahlenbereichsbeschränkungen von BlitzBasic zum Tragen kommen.
Wenn man das Programm unterbricht und dann weiterlaufen lassen will, muss man zudem den Wert von der Startzahl z und der txt-nummerierung ändern.

BlitzBasic: [AUSKLAPPEN]


;** März 2005
;** by Triton
;** www.silizium-net.de
Graphics 400,300,32,2
AppTitle(\"Primzahlen\")
txt=1
DeleteFile(\"primzahlen\"+txt+\".txt\")
dat=WriteFile(\"primzahlen\"+txt+\".txt\")
CloseFile dat
dat=OpenFile(\"primzahlen\"+txt+\".txt\")
z=1 ;Startzahl (wer hoch beginnen möchte, nehme 1002888199)
t1=MilliSecs()

While Not KeyDown(1)
zahl$ = Str(z) 
If primzahl(zahl$) = 1 Then
	WriteLine dat,zahl$
	i=i+1
End If
If i Mod 500 = 0 Then Print zahl$
If i=500000 Then
	t2=MilliSecs()-t1
	min=t2/60000
	sek=(t2 Mod 60000)/1000
	If min=1 Then WriteLine dat,\"Benötigte Zeit: \"+min+\" Minute, \"+sek+\" Sekunden\"
	If min>1 Then WriteLine dat,\"Benötigte Zeit: \"+min+\" Minuten, \"+sek+\" Sekunden\"
	t1=MilliSecs()
	CloseFile dat
	dat=WriteFile(\"primzahlen\"+txt+\".txt\")
	txt=txt+1
	i=0
End If
z=z+2
Wend


;---
Function primzahl$(zahl$)
If zahl$=1 Then Return 0
If zahl$=2 Or zahl$=3 Or zahl$=5 Then Return 1
If Right(zahl$,1) = 5 Then Return 0
For stelle=1 To Len(zahl$)
	ziffer$=Mid(zahl$,stelle,1)
	quersumme=quersumme+Int(ziffer$)
Next
If quersumme Mod 3 = 0 Then Return 0	;schließt Zahl aus, wenn 3/9 = Teiler
wz=Int(zahl$)
For i=3 To Sqr(wz) Step 2
	If wz Mod i = 0 Then Return 0
Next
Return 1
End Function

Coding: silizium-net.de | Portfolio: Triton.ch.vu

Zuletzt bearbeitet von Triton am Di, Jun 07, 2005 0:08, insgesamt 5-mal bearbeitet

	regaa	So, Jun 05, 2005 19:19 Antworten mit Zitat
Kewle Sache aber eins möchte ich wissen, aber bitte nicht schlagen: Wozu sind Primzahlen für Spiele oder andere Anwendungen gut?
UltraMixer Professional 3 - Download QB,HTML,CSS,JS,PHP,SQL,>>B2D,B3D,BP,BlitzMax,C,C++,Java,C#,VB6 , C#, VB.Net

regaa

So, Jun 05, 2005 19:19
Antworten mit Zitat

Kewle Sache aber eins möchte ich wissen, aber bitte nicht schlagen: Wozu sind Primzahlen für Spiele oder andere Anwendungen gut?

UltraMixer Professional 3 - Download
QB,HTML,CSS,JS,PHP,SQL,>>B2D,B3D,BP,BlitzMax,C,C++,Java,C#,VB6 , C#, VB.Net

	Ctuchik	So, Jun 05, 2005 22:22 Antworten mit Zitat
Warum benutzt du so eine komplizierte Funktion um festzustellen ob es eine Primzahl ist? Ich würd das so machen, ist wesentlich einfacher! EDIT: Ich ersetzte mal Syntax durch Code, dadurch wirds zwar schlechter lesbar aber der Thread lädt schneller! Code: [AUSKLAPPEN] [EINKLAPPEN] Graphics 400,300,32,2 AppTitle("Primzahlen") Const PRINTNUMBERS = True DeleteFile("primzahlen.txt") dat=WriteFile("primzahlen.txt") start=3 ;Startzahl If start < 2 Then start = 2 If start = 2 Then WriteLine dat,"2" start = start + (1-(start Mod 2)) ende=10000000 ;Endzahl If (Not PRINTNUMBERS) Then Print "Berechne Primzahlen zwischen "+start+" und "+ende+" bitte warten..." t1=MilliSecs() For zahl=start To ende Step 2 If primzahl(zahl) Then WriteLine dat,Str(zahl) i = i + 1 End If If PRINTNUMBERS Then If i Mod 500 = 0 Then Print zahl End If If KeyHit(1) Then cancel = True Exit End If Next t1=MilliSecs()-t1 min=t1/60000 sek=(t1 Mod 60000)/1000 WriteLine dat,"Benötigte Zeit: "+min+" Minuten, "+sek+" Sekunden." If cancel Then Print "Abgebrochen durch den Benutzer!" Else Print "Fertig!" End If Print "Benötigte Zeit: "+min+" Minuten, "+sek+" Sekunden." CloseFile dat FlushKeys() WaitKey() End Function primzahl(zahl) wurzel = Sqr(zahl) For teiler=3 To wurzel Step 2 If (zahl Mod teiler = 0) Then Return False Next Return True End Function
Zu den Nebenwirkungen gehören trockener Mund, Übelkeit, Erbrechen, Harnstau, schmerzhafter rektaler Juckreiz, Halluzinationen, Demenz, Psychose, Koma, Tod und Mundgeruch! Magie eignet sich nicht für alle! Fraget euren Arzt oder Apotheker!

Ctuchik

So, Jun 05, 2005 22:22
Antworten mit Zitat

Warum benutzt du so eine komplizierte Funktion um festzustellen ob es eine Primzahl ist?
Ich würd das so machen, ist wesentlich einfacher!

EDIT: Ich ersetzte mal Syntax durch Code, dadurch wirds zwar schlechter lesbar aber der Thread lädt schneller!

Code: [AUSKLAPPEN]

Graphics 400,300,32,2
AppTitle("Primzahlen")
Const PRINTNUMBERS = True

DeleteFile("primzahlen.txt")
dat=WriteFile("primzahlen.txt")
start=3 ;Startzahl
If start < 2 Then start = 2
If start = 2 Then WriteLine dat,"2"
start = start + (1-(start Mod 2))
ende=10000000 ;Endzahl
If (Not PRINTNUMBERS) Then Print "Berechne Primzahlen zwischen "+start+" und "+ende+" bitte warten..."
t1=MilliSecs()

For zahl=start To ende Step 2
If primzahl(zahl) Then
WriteLine dat,Str(zahl)
i = i + 1
End If
If PRINTNUMBERS Then
If i Mod 500 = 0 Then Print zahl
End If
If KeyHit(1) Then
cancel = True
Exit
End If
Next

t1=MilliSecs()-t1
min=t1/60000
sek=(t1 Mod 60000)/1000
WriteLine dat,"Benötigte Zeit: "+min+" Minuten, "+sek+" Sekunden."
If cancel Then
Print "Abgebrochen durch den Benutzer!"
Else
Print "Fertig!"
End If
Print "Benötigte Zeit: "+min+" Minuten, "+sek+" Sekunden."
CloseFile dat
FlushKeys()
WaitKey()

End

Function primzahl(zahl)
wurzel = Sqr(zahl)
For teiler=3 To wurzel Step 2
If (zahl Mod teiler = 0) Then Return False
Next
Return True
End Function

Zu den Nebenwirkungen gehören trockener Mund, Übelkeit, Erbrechen, Harnstau, schmerzhafter rektaler Juckreiz, Halluzinationen, Demenz, Psychose, Koma, Tod und Mundgeruch!
Magie eignet sich nicht für alle!
Fraget euren Arzt oder Apotheker!

Zuletzt bearbeitet von Ctuchik am Di, Jun 07, 2005 0:32, insgesamt einmal bearbeitet

	Triton	Mo, Jun 06, 2005 17:02 Antworten mit Zitat
Weil meins etwa 20% schneller sein dürfte? Man kann gewisse Zahlen als Teiler schnell ausschließen. Namentlich wären dies 2,(3),4,5,6,8,(9). Du schließt dagegen nur die geraden Zahlen aus, womit deins langsamer ist. Außerdem gibst du einen Endwert an. Wozu? Ich hab das Programm geschrieben um - theoretisch (die Zahlenbereichsbeschränkungen von BB verhindern dies) - unendlich viele Primzahlen zu ermitteln. Daher auch die Spielerei mit der Quersumme bei der Überprüfung auf 3 oder 9 als Teiler. @regaa: hmm, gute Frage Man kann jede Zahl als Produkt aus Primfaktoren darstellen, somit kann man z.B zu Flächen deren Größe bekannt ist Seitenlängen zuweisen. Ansonsten: siehe wikipedia.de oder so Ansonsten braucht man die Überwiegend im Bereich der Kryptographie.
Coding: silizium-net.de \| Portfolio: Triton.ch.vu

Triton

Mo, Jun 06, 2005 17:02
Antworten mit Zitat

Weil meins etwa 20% schneller sein dürfte?
Man kann gewisse Zahlen als Teiler schnell ausschließen.

Namentlich wären dies 2,(3),4,5,6,8,(9). Du schließt dagegen nur die geraden Zahlen aus, womit deins langsamer ist.

Außerdem gibst du einen Endwert an. Wozu?
Ich hab das Programm geschrieben um - theoretisch (die Zahlenbereichsbeschränkungen von BB verhindern dies) - unendlich viele Primzahlen zu ermitteln. Daher auch die Spielerei mit der Quersumme bei der Überprüfung auf 3 oder 9 als Teiler.

@regaa: hmm, gute Frage Smile

Man kann jede Zahl als Produkt aus Primfaktoren darstellen, somit kann man z.B zu Flächen deren Größe bekannt ist Seitenlängen zuweisen.
Ansonsten: siehe wikipedia.de oder so Rolling Eyes

Ansonsten braucht man die Überwiegend im Bereich der Kryptographie.

Coding: silizium-net.de | Portfolio: Triton.ch.vu

	Ctuchik	Mo, Jun 06, 2005 18:22 Antworten mit Zitat
Also du Obergrenze kann man natürlich auch rausnehmen, daran solls nicht scheitern! Ich denke aber nicht, dass deins schneller ist! Du arbeitest mit Strings und die sind generell langsamer als Integer! Bei mir werden keine geraden Zahlen überprüft, die fallen also schomnal raus. 3 muss ich nicht über die Quersumme ausschließen, weil die 3 danach sowieso als allererstes getestet wird und dann die 5. In beiden Fällen wird die Funktion dann ja sofort mit Return verlassen, die Schleife läuft ja nur solange bis der erste Teiler gefunden ist! Aber zum Vergleich kannst du bei deinem ja mal auch ne Obergrenze einbauen und wir schauen wie lange es dauert z.B. von 3 bis 10000000 alle Primzahlen zu finden. Mit meinem auf einem P4 3000Mhz etwa 20 Sekunden! EDIT: Was mir bei deinem grad noch aufgefallen ist: Wenn du bei 2 anfängst und immer 2 hochzählst wirst keine Primzahlen mehr finden, weil dann nur gerade zahlen kommen. Du solltest also mit einer ungeraden Zahl anfangen! MfG Ctuchik
Zu den Nebenwirkungen gehören trockener Mund, Übelkeit, Erbrechen, Harnstau, schmerzhafter rektaler Juckreiz, Halluzinationen, Demenz, Psychose, Koma, Tod und Mundgeruch! Magie eignet sich nicht für alle! Fraget euren Arzt oder Apotheker!

Ctuchik

Mo, Jun 06, 2005 18:22
Antworten mit Zitat

Also du Obergrenze kann man natürlich auch rausnehmen, daran solls nicht scheitern!

Ich denke aber nicht, dass deins schneller ist!
Du arbeitest mit Strings und die sind generell langsamer als Integer!
Bei mir werden keine geraden Zahlen überprüft, die fallen also schomnal raus.
3 muss ich nicht über die Quersumme ausschließen, weil die 3 danach sowieso als allererstes getestet wird und dann die 5. In beiden Fällen wird die Funktion dann ja sofort mit Return verlassen, die Schleife läuft ja nur solange bis der erste Teiler gefunden ist!

Aber zum Vergleich kannst du bei deinem ja mal auch ne Obergrenze einbauen und wir schauen wie lange es dauert z.B. von 3 bis 10000000 alle Primzahlen zu finden. Mit meinem auf einem P4 3000Mhz etwa 20 Sekunden!

EDIT: Was mir bei deinem grad noch aufgefallen ist: Wenn du bei 2 anfängst und immer 2 hochzählst wirst keine Primzahlen mehr finden, weil dann nur gerade zahlen kommen. Du solltest also mit einer ungeraden Zahl anfangen!

MfG Ctuchik

	Triton	Mo, Jun 06, 2005 22:26 Antworten mit Zitat
Ja, ich werde morgen mal einen Speed-Check machen. Zitat: Du arbeitest mit Strings und die sind generell langsamer als Integer! Wie gesagt, sowohl der test auf 3 als teiler, als auch die ganze Abwicklung über Strings habe ich eingebaut, weil ich eigentlich unendlich große Primzahlen ermitteln wollte (bau ich irgendwann nochmal ein). Dazu werde ich aber noch + - / * mod und die wurzelfkt per hand coden müssen. Zitat: Bei mir werden keine geraden Zahlen überprüft, die fallen also schomnal raus. Jo, bei mir auch nicht. Ebensowenig die 5 und viele 3 und 9er-Zahlen Zitat: 3 muss ich nicht über die Quersumme ausschließen, weil die 3 danach sowieso als allererstes getestet wird und dann die 5. Stimmt, würde in der tat reichen, wenn ich mit 7 anfange. Zitat: EDIT: Was mir bei deinem grad noch aufgefallen ist: Wenn du bei 2 anfängst und immer 2 hochzählst wirst keine Primzahlen mehr finden, weil dann nur gerade zahlen kommen. Du solltest also mit einer ungeraden Zahl anfangen! Es spielt keine Rolle, bei welcher Zahl man bei mir anfängt. Jede natürliche Zahl wird akzeptiert
Coding: silizium-net.de \| Portfolio: Triton.ch.vu

Triton

Mo, Jun 06, 2005 22:26
Antworten mit Zitat

Ja, ich werde morgen mal einen Speed-Check machen.

Zitat:

Du arbeitest mit Strings und die sind generell langsamer als Integer!

Wie gesagt, sowohl der test auf 3 als teiler, als auch die ganze Abwicklung über Strings habe ich eingebaut, weil ich eigentlich unendlich große Primzahlen ermitteln wollte (bau ich irgendwann nochmal ein). Dazu werde ich aber
noch + - / * mod und die wurzelfkt per hand coden müssen.

Zitat:

Bei mir werden keine geraden Zahlen überprüft, die fallen also schomnal raus.

Jo, bei mir auch nicht. Ebensowenig die 5 und viele 3 und 9er-Zahlen Smile

Zitat:

3 muss ich nicht über die Quersumme ausschließen, weil die 3 danach sowieso als allererstes getestet wird und dann die 5.

Stimmt, würde in der tat reichen, wenn ich mit 7 anfange.

Zitat:

EDIT: Was mir bei deinem grad noch aufgefallen ist: Wenn du bei 2 anfängst und immer 2 hochzählst wirst keine Primzahlen mehr finden, weil dann nur gerade zahlen kommen. Du solltest also mit einer ungeraden Zahl anfangen!

Es spielt keine Rolle, bei welcher Zahl man bei mir anfängt. Jede natürliche Zahl wird
akzeptiert Wink

Coding: silizium-net.de | Portfolio: Triton.ch.vu

	Ctuchik	Mo, Jun 06, 2005 23:57 Antworten mit Zitat
BlitzBasic: [AUSKLAPPEN] [EINKLAPPEN] If Int(Right(zahl$,1)) Mod 2 = 0 Then Return 0 ;schließt Zahl aus, wenn 0,2,4,6,8 = Endung Wenn du sowieso in Zweierschritten zählst (z=z+2), fallen gerade Zahlen doch raus, warum überprüfst du sie dann noch? Zitat: Es spielt keine Rolle, bei welcher Zahl man bei mir anfängt. Jede natürliche Zahl wird akzeptiert Wenn man den Code so wie oben 1:1 kopiert und ausführt wird lediglich die 2 in die Datei geschrieben, da er zählt: 2,4,6,8,10,12,... (z=z+2, s.o.) und gerade Zahlen ja ausser der 2 keine Primzahlen sind! Also entweder z=z+1 schreiben oder bei einer ungeraden Zahl anfangen! Zitat: die ganze Abwicklung über Strings habe ich eingebaut, weil ich eigentlich unendlich große Primzahlen ermitteln wollte Das ist ein Argument! Da gabs doch mal die Rechenfunktionen für String-Zahlen von Rallimen glaub ich oder? Die könntest du dann ja verwenden oder anpassen! MfG Ctuchik
Zu den Nebenwirkungen gehören trockener Mund, Übelkeit, Erbrechen, Harnstau, schmerzhafter rektaler Juckreiz, Halluzinationen, Demenz, Psychose, Koma, Tod und Mundgeruch! Magie eignet sich nicht für alle! Fraget euren Arzt oder Apotheker!

Ctuchik

Mo, Jun 06, 2005 23:57
Antworten mit Zitat

BlitzBasic: [AUSKLAPPEN]

If Int(Right(zahl$,1)) Mod 2 = 0 Then Return 0          ;schließt Zahl aus, wenn 0,2,4,6,8 = Endung

Wenn du sowieso in Zweierschritten zählst (z=z+2), fallen gerade Zahlen doch raus, warum überprüfst du sie dann noch? Wink

Zitat:

Es spielt keine Rolle, bei welcher Zahl man bei mir anfängt. Jede natürliche Zahl wird
akzeptiert

Wenn man den Code so wie oben 1:1 kopiert und ausführt wird lediglich die 2 in die Datei geschrieben, da er zählt: 2,4,6,8,10,12,... (z=z+2, s.o.) und gerade Zahlen ja ausser der 2 keine Primzahlen sind!
Also entweder z=z+1 schreiben oder bei einer ungeraden Zahl anfangen!
Zitat:

die ganze Abwicklung über Strings habe ich eingebaut, weil ich eigentlich unendlich große Primzahlen ermitteln wollte

Das ist ein Argument! Da gabs doch mal die Rechenfunktionen für String-Zahlen von Rallimen glaub ich oder? Die könntest du dann ja verwenden oder anpassen!

MfG Ctuchik

	Triton	Di, Jun 07, 2005 0:03 Antworten mit Zitat
So, hab noch bischen zumgetüftelt und einfach einen Primzahltest geschrieben, der deinen Kriterien entspricht: BlitzBasic: [AUSKLAPPEN] [EINKLAPPEN] ; Juni 2005 ; by Triton ; www.silizium-net.de ; High-Speed-Version Graphics 400,300,32,2 AppTitle(\"Primzahlen\") zahl=3 endzahl=1000000 ;7368809 Global j=Sqr(endzahl) Global a1,i,t2 Dim pz(j) Print \"Ermittle Primzahlen von \"+Zahl+\" bis \"+endzahl+\".\" Print \"...\" DeleteFile(\"primzahlen\"+txt+\".txt\") dat=WriteFile(\"primzahlen\"+txt+\".txt\") CloseFile dat dat=OpenFile(\"primzahlen\"+txt+\".txt\") WriteLine dat,\"2\" t1=MilliSecs() For z1=3 To j Step 2 If primzahlalt(z1) = 1 Then pz(a1)=z1 a1=a1+1 WriteLine dat,z1 End If Next While Not KeyDown(1) If primzahl(zahl) = 1 Then WriteLine dat,Str(zahl) i=i+1 End If ;If i Mod 10000 = 0 Then Print zahl If zahl>endzahl Then t2=MilliSecs()-t1 WriteLine dat, i+a1+\" Primzahlen gefunden.\" WriteLine dat,\"Es hat \"+t2+\" ms gedauert.\" t1=MilliSecs() CloseFile dat stats() End If zahl=zahl+2 Wend ;--- Function stats() Print i+a1+\" Primzahlen gefunden.\" Print \"Es hat \"+t2+\" ms gedauert.\" Print \"\" Print \"Bye.\" WaitKey End End Function ;--- Function primzahl(zahl) For i2=0 To a1-1 Step 1 If (zahl Mod pz(i2) = 0) Then Return 0 Next Return 1 End Function ;--- Function primzahlalt(zahl) For teiler=3 To Sqr(zahl) Step 2 If (zahl Mod teiler = 0) Then Return 0 Next Return 1 End Function Für die Primzahlen bis 1 mio dauert es 578 ms (deiner 1162 ms). Für die ersten 500.000 Pz (bis 7368811) dauert es bei mir 7365 ms und bei dir 16036 ms. Bei meiner älteren Version hats noch 80000 ms gedauert. Das werde ich aber auch noch deutlich unter 30 sek bringen können - auch mit Strings. edit-- Danke, dass du mich auf diese Fehler aufmerksam gemacht hast. Hab sie korrigiert.
Coding: silizium-net.de \| Portfolio: Triton.ch.vu

Triton

Di, Jun 07, 2005 0:03
Antworten mit Zitat

So, hab noch bischen zumgetüftelt und einfach einen Primzahltest geschrieben, der deinen Kriterien entspricht:

BlitzBasic: [AUSKLAPPEN]


;** Juni 2005
;** by Triton
;** www.silizium-net.de
;** High-Speed-Version
Graphics 400,300,32,2
AppTitle(\"Primzahlen\")
zahl=3
endzahl=1000000 ;7368809
Global j=Sqr(endzahl)
Global a1,i,t2
Dim pz(j)

Print \"Ermittle Primzahlen von \"+Zahl+\" bis \"+endzahl+\".\"
Print \"...\"

DeleteFile(\"primzahlen\"+txt+\".txt\")
dat=WriteFile(\"primzahlen\"+txt+\".txt\")
CloseFile dat
dat=OpenFile(\"primzahlen\"+txt+\".txt\")
WriteLine dat,\"2\"
t1=MilliSecs()

For z1=3 To j Step 2
	If primzahlalt(z1) = 1 Then 
		pz(a1)=z1
		a1=a1+1
		WriteLine dat,z1
	End If
Next

While Not KeyDown(1)
If primzahl(zahl) = 1 Then
	WriteLine dat,Str(zahl)
	i=i+1
End If
;If i Mod 10000 = 0 Then Print zahl
If zahl>endzahl Then
	t2=MilliSecs()-t1
	WriteLine dat, i+a1+\" Primzahlen gefunden.\"
	WriteLine dat,\"Es hat \"+t2+\" ms gedauert.\"
	t1=MilliSecs()
	CloseFile dat
	stats()
End If
zahl=zahl+2
Wend

;---
Function stats()
Print i+a1+\" Primzahlen gefunden.\"
Print \"Es hat \"+t2+\" ms gedauert.\"
Print \"\"
Print \"Bye.\"
WaitKey
End 
End Function 

;---
Function primzahl(zahl)
For i2=0 To a1-1 Step 1				
	If (zahl Mod pz(i2) = 0) Then Return 0
Next
Return 1
End Function


;---
Function primzahlalt(zahl) 
For teiler=3 To Sqr(zahl) Step 2 
	If (zahl Mod teiler = 0) Then Return 0 
Next 
Return 1 
End Function

Für die Primzahlen bis 1 mio dauert es 578 ms (deiner 1162 ms).
Für die ersten 500.000 Pz (bis 7368811) dauert es bei mir 7365 ms und bei dir 16036 ms.

Bei meiner älteren Version hats noch 80000 ms gedauert. Das werde ich aber auch noch deutlich unter 30 sek bringen können - auch mit Strings.

edit--
Danke, dass du mich auf diese Fehler aufmerksam gemacht hast. Hab sie korrigiert.

Coding: silizium-net.de | Portfolio: Triton.ch.vu

Zuletzt bearbeitet von Triton am Sa, Jun 11, 2005 17:52, insgesamt 2-mal bearbeitet

	Ctuchik	Di, Jun 07, 2005 0:24 Antworten mit Zitat
Deine neue Version benutzt ein sehr schönes Prinzip! Das Zwischenspeichern von Primzahlen macht das ganze natürlich um einiges schneller! Allerdings waren ein paar kleine Fehler drin, so dass er teilweise falsche Zahlen als Primzahlen angezeigt hat! Ich habe die Fehler mal behoben und es müssten eigentlich auch noch ein paar ms drin sein, weil er nach der ersten Schleife, die die Primzahlen bis zur Wurzel der Endzahl berechnet, dann ja direkt dahinter einsteigen kann, und die Zahlen nicht nochmal berechnen muss! MfG Ctuchik EDIT: Code nochmal rausgenommen, entweder du hast die Fehler grad behoben oder ich hab grad was falsch gemacht, jedenfalls funktioniert deins jetzt so wies soll! Beim ersten mal hat er mir teilweise auch gerade Zahlen ausgespuckt! EDIT2: Ok der oben genannte Geschwindigkeitsnachteil existiert noch, und zwar überprüfst du sämtliche schon in den Array geschrieben Primzahlen doppelt! Deswegen einfach vor die While-Schleife: BlitzBasic: [AUSKLAPPEN] [EINKLAPPEN] zahl = j If zahl Mod 2 = 0 Then zahl = zahl + 1 denn du musst erst ab j weiter überprüfen!
Zu den Nebenwirkungen gehören trockener Mund, Übelkeit, Erbrechen, Harnstau, schmerzhafter rektaler Juckreiz, Halluzinationen, Demenz, Psychose, Koma, Tod und Mundgeruch! Magie eignet sich nicht für alle! Fraget euren Arzt oder Apotheker!

Ctuchik

Di, Jun 07, 2005 0:24
Antworten mit Zitat

Deine neue Version benutzt ein sehr schönes Prinzip!
Das Zwischenspeichern von Primzahlen macht das ganze natürlich um einiges schneller!
Allerdings waren ein paar kleine Fehler drin, so dass er teilweise falsche Zahlen als Primzahlen angezeigt hat!
Ich habe die Fehler mal behoben und es müssten eigentlich auch noch ein paar ms drin sein, weil er nach der ersten Schleife, die die Primzahlen bis zur Wurzel der Endzahl berechnet, dann ja direkt dahinter einsteigen kann, und die Zahlen nicht nochmal berechnen muss!

MfG Ctuchik

EDIT: Code nochmal rausgenommen, entweder du hast die Fehler grad behoben oder ich hab grad was falsch gemacht, jedenfalls funktioniert deins jetzt so wies soll! Beim ersten mal hat er mir teilweise auch gerade Zahlen ausgespuckt!

EDIT2: Ok der oben genannte Geschwindigkeitsnachteil existiert noch, und zwar überprüfst du sämtliche schon in den Array geschrieben Primzahlen doppelt!
Deswegen einfach vor die While-Schleife:
BlitzBasic: [AUSKLAPPEN]

zahl = j
If zahl Mod 2 = 0 Then zahl = zahl + 1

denn du musst erst ab j weiter überprüfen!

Übersicht

BlitzBasic

Codearchiv

Nach Oben

BlitzBasic Portal

Primzahlen ermitteln

Betreff: Primzahlen ermitteln