Primzahlen

Übersicht

BlitzBasic

Allgemein

Gehe zu Seite 1, 2 Weiter

	dominik Betreff: Primzahlen	Sa, März 12, 2005 15:37 Antworten mit Zitat
Nachdem ich letzte Woche (oder warsschon vor 2?) mal was von dem Augenartzt mit seinen 14. Rechner und der größten Primzahl gelesen hab, dachte ich schreib ich auch mal nen Prog mit dem man Primzahlen berechen kann. Des is mein Prog. BlitzBasic: [AUSKLAPPEN] [EINKLAPPEN] If FileType(\"datei_prim.txt\") <> 1 Then datei_prim = WriteFile(\"datei_prim.txt\") Z = 1 Else datei_prim = OpenFile(\"datei_prim.txt\") Repeat letztzahl = ReadLine(datei_prim) Until Eof(datei_prim) Z = letztzahl EndIf primzahl = True Repeat Z = Z + 1 i% = 2 While i% < Z And primzahl = True rest% = Z Mod i% Select rest% Case 0 primzahl = False Default primzahl = True End Select i% = i% + 1 Wend If primzahl = True Then Print Z WriteLine datei_prim, Z EndIf primzahl = True Forever CloseFile datei bisher noch ganz einfach. Meine bisher größt errechnete Zahl is 300191. Wie könnte ich den am besten überprüfen ob mein Prog auch wirklich richtig arbeitet? Ich hab hier noch so nen Matheduden und in dem stehen die ersten 100, die auch mit meinen Ergebnissen übereinstimmen, drinnen.
BB+ 1.41\|Sempron 2.8\|geforce fx5200\|1GB DDR\|XP home SP2 / prof.

dominik

Betreff: Primzahlen

Sa, März 12, 2005 15:37
Antworten mit Zitat

Nachdem ich letzte Woche (oder warsschon vor 2?) mal was von dem Augenartzt mit seinen 14. Rechner und der größten Primzahl gelesen hab, dachte ich schreib ich auch mal nen Prog mit dem man Primzahlen berechen kann.
Des is mein Prog.
BlitzBasic: [AUSKLAPPEN]

If FileType(\"datei_prim.txt\") <> 1 Then
  datei_prim = WriteFile(\"datei_prim.txt\")
  Z = 1
Else
  datei_prim = OpenFile(\"datei_prim.txt\")
  Repeat
  letztzahl = ReadLine(datei_prim)
  Until Eof(datei_prim)
  Z = letztzahl
EndIf

primzahl = True
Repeat
  Z = Z + 1
  i% = 2

  While i% < Z And primzahl = True
    rest% = Z Mod i%

    Select rest% 
      Case 0
        primzahl = False
      Default
        primzahl = True
    End Select 

    i% = i% + 1

  Wend
  
  If primzahl = True Then 
    Print Z 
    WriteLine datei_prim, Z
  EndIf
  primzahl = True
Forever
CloseFile datei

bisher noch ganz einfach. Meine bisher größt errechnete Zahl is 300191.
Wie könnte ich den am besten überprüfen ob mein Prog auch wirklich richtig arbeitet?
Ich hab hier noch so nen Matheduden und in dem stehen die ersten 100, die auch mit meinen Ergebnissen übereinstimmen, drinnen.

BB+ 1.41|Sempron 2.8|geforce fx5200|1GB DDR|XP home SP2 / prof.

	NetPad	Sa, März 12, 2005 16:12 Antworten mit Zitat
ist eine primzahl

NetPad

Sa, März 12, 2005 16:12
Antworten mit Zitat

ist eine primzahl

	dominik	Sa, März 12, 2005 16:27 Antworten mit Zitat
ja hast ma schnell im Kopf nachgerechnet oder was?
BB+ 1.41\|Sempron 2.8\|geforce fx5200\|1GB DDR\|XP home SP2 / prof.

dominik

Sa, März 12, 2005 16:27
Antworten mit Zitat

ja hast ma schnell im Kopf nachgerechnet oder was?

BB+ 1.41|Sempron 2.8|geforce fx5200|1GB DDR|XP home SP2 / prof.

	Rallimen Sieger des 30-EUR-Wettbewerbs	Sa, März 12, 2005 16:55 Antworten mit Zitat
habs überprüft, und rechnet auch richtig! Allerdings brauchst nur die Ungraden zu testen und das nur rauf bis zur Wurzel der Zahl, denn ab da wiederholt sich alles nur. Wenn die Quersumme durch 3 teilbar ist dann ist es auch keine Primzahl. Wenn du das berücksichtigst dann gehts auch schneller mit der Rechnerrei, das Problem beginnt erst ab Zahlen die größer als Integer 4Byte sind hier noch ein paar Testzahlen: 8999849 8999867 8999897 8999899 8999927 8999957 8999971 8999981 8999993
[BB2D \| BB3D \| BB+]

Rallimen

Sieger des 30-EUR-Wettbewerbs

Sa, März 12, 2005 16:55
Antworten mit Zitat

habs überprüft, und rechnet auch richtig!
Allerdings brauchst nur die Ungraden zu testen und das nur rauf bis zur Wurzel der Zahl, denn ab da wiederholt sich alles nur.
Wenn die Quersumme durch 3 teilbar ist dann ist es auch keine Primzahl.
Wenn du das berücksichtigst dann gehts auch schneller mit der Rechnerrei, das Problem beginnt erst ab Zahlen die größer als Integer 4Byte sind
hier noch ein paar Testzahlen:
8999849 8999867 8999897 8999899 8999927
8999957 8999971 8999981 8999993

[BB2D | BB3D | BB+]

	Triton	Sa, März 12, 2005 16:59 Antworten mit Zitat
Es ist tatsächlich eine. Nützlich zur berechnung von Primzahlen ist es noch, von vornerein 0,2,4,5,6,8,9 als Teiler auszuschließen. Wenn die Endzahl 0,2,4,6 oder 8 ist, ist es keine Primzahl, wenn die Endzahl 5 ist, auch nicht, wenn die Quersumme durch 3 Teilbar ist auch nicht wenn die quersumme durch 9 teilbar ist auch nicht. (wird aber schon durch 3 abgedeckt.. ) Verringert den Rechenaufwand schonmal um etwa die Hälfte.
Coding: silizium-net.de \| Portfolio: Triton.ch.vu

Triton

Sa, März 12, 2005 16:59
Antworten mit Zitat

Es ist tatsächlich eine.

Nützlich zur berechnung von Primzahlen ist es noch, von vornerein
0,2,4,5,6,8,9 als Teiler auszuschließen.

Wenn die Endzahl 0,2,4,6 oder 8 ist, ist es keine Primzahl,
wenn die Endzahl 5 ist, auch nicht,
wenn die Quersumme durch 3 Teilbar ist auch nicht
wenn die quersumme durch 9 teilbar ist auch nicht. (wird aber schon durch 3 abgedeckt.. Rolling Eyes

)

Verringert den Rechenaufwand schonmal um etwa die Hälfte.

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

Zuletzt bearbeitet von Triton am Sa, März 12, 2005 17:14, insgesamt einmal bearbeitet

	dominik	Sa, März 12, 2005 17:06 Antworten mit Zitat
Welches Problem? Und was is mit den Testzahlen? Bis 8 Mio. dauerts noch nen bischen bin gard erst bei 417017.
BB+ 1.41\|Sempron 2.8\|geforce fx5200\|1GB DDR\|XP home SP2 / prof.

dominik

Sa, März 12, 2005 17:06
Antworten mit Zitat

Welches Problem?
Und was is mit den Testzahlen? Bis 8 Mio. dauerts noch nen bischen bin gard erst bei 417017. Very Happy

BB+ 1.41|Sempron 2.8|geforce fx5200|1GB DDR|XP home SP2 / prof.

	BladeRunner Moderator	Sa, März 12, 2005 17:11 Antworten mit Zitat
hust wenn die Quersumme durch 9 teilbar ist ist sie garantiert durch 3 teilbar. der test ist also eigentlich unnötig.
Zu Diensten, Bürger. Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3 Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64 B3D BMax MaxGUI Stolzer Gewinner des BAC#48, #52 & #92

BladeRunner

Moderator

Sa, März 12, 2005 17:11
Antworten mit Zitat

*hust* wenn die Quersumme durch 9 teilbar ist ist sie garantiert durch 3 teilbar. der test ist also eigentlich unnötig.

Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3
Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64
B3D BMax MaxGUI
Stolzer Gewinner des BAC#48, #52 & #92

	Triton	Sa, März 12, 2005 17:12 Antworten mit Zitat
Wenn die Zahlen zu groß werden, kann man weder die Teiler noch die Wurzel bilden. Dann muss man sich eigene Zahlen/Rechensysteme schreiben, die über String-Operationen laufen. -- @BR: Stimmt natürlich. Übersehen. -- Ach ja, die rekordzahl ist im Moment 2^24 036 583-1 Eine Zahl mit >7 mio Stellen.
Coding: silizium-net.de \| Portfolio: Triton.ch.vu

Triton

Sa, März 12, 2005 17:12
Antworten mit Zitat

Wenn die Zahlen zu groß werden, kann man weder die Teiler noch die Wurzel bilden.

Dann muss man sich eigene Zahlen/Rechensysteme schreiben, die über String-Operationen laufen.

--
@BR: Stimmt natürlich. Übersehen.

--
Ach ja, die rekordzahl ist im Moment 2^24 036 583-1
Eine Zahl mit >7 mio Stellen.

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

	Absoluter Beginner	Sa, März 12, 2005 17:59 Antworten mit Zitat
Wikipedia hat Folgendes geschrieben: Die derzeit größte bekannte Primzahl ist 2^25.964.951 - 1, eine Zahl mit 7.816.230 Dezimalstellen, gefunden im Februar 2005 von Dr. Martin Nowak....
Error Inside!

Absoluter Beginner

Sa, März 12, 2005 17:59
Antworten mit Zitat

Wikipedia hat Folgendes geschrieben:

Die derzeit größte bekannte Primzahl ist 2^25.964.951 - 1, eine Zahl mit 7.816.230 Dezimalstellen, gefunden im Februar 2005 von Dr. Martin Nowak....

Error Inside!

	NetPad	Sa, März 12, 2005 19:08 Antworten mit Zitat
hmmmm....mein rechner ist mit dieser "primzahl" aber nicht einverstanden. könnte jedoch an seinem algorithmus liegen

NetPad

Sa, März 12, 2005 19:08
Antworten mit Zitat

hmmmm....mein rechner ist mit dieser "primzahl" aber nicht einverstanden. könnte jedoch an seinem algorithmus liegen

	Rallimen Sieger des 30-EUR-Wettbewerbs	So, März 13, 2005 2:17 Antworten mit Zitat
Integer gehen nur bis +2147483647 also max. 9 stellen, Für die größeren Zahlen brauchst du einen anderen Algo ,dee auch unendlich viele Stellen benutzten kann! dominik: In welchem Bereich brauchte die Zahlen zum vergleichen, denn alle wollte ich nicht hier rein schreiben, das Sprengt wohl evt das Forum! Habe gerade mal mein Proggi laufen lassen und es dauerte fast 5 Min bis 8 Mio Zahlen das sind als Writeline geschriebene zahlen knapp 5MB Ungrade Zahlen sind nicht durch grade Zahlen teilbar, das beschleunigt die Rechnungen auch noch!
[BB2D \| BB3D \| BB+]

Rallimen

Sieger des 30-EUR-Wettbewerbs

So, März 13, 2005 2:17
Antworten mit Zitat

Integer gehen nur bis +2147483647 also max. 9 stellen, Für die größeren Zahlen brauchst du einen anderen Algo ,dee auch unendlich viele Stellen benutzten kann!

dominik:
In welchem Bereich brauchte die Zahlen zum vergleichen, denn alle wollte ich nicht hier rein schreiben, das Sprengt wohl evt das Forum!
Habe gerade mal mein Proggi laufen lassen und
es dauerte fast
5 Min bis 8 Mio Zahlen
das sind als Writeline geschriebene zahlen knapp 5MB

Ungrade Zahlen sind nicht durch grade Zahlen teilbar, das beschleunigt die Rechnungen auch noch!

[BB2D | BB3D | BB+]

	dominik	So, März 13, 2005 12:22 Antworten mit Zitat
Was in 5 min. bis zu 8 Mio????? Den Code will ich auch ma sehen! Post ma bitte. Bin grad erst bei 1000003 angekommen. Meine erste 6 Stellige Zahl. 8)
BB+ 1.41\|Sempron 2.8\|geforce fx5200\|1GB DDR\|XP home SP2 / prof.

dominik

So, März 13, 2005 12:22
Antworten mit Zitat

Was in 5 min. bis zu 8 Mio?????
Den Code will ich auch ma sehen! Post ma bitte.

Bin grad erst bei 1000003 angekommen.
Meine erste 6 Stellige Zahl. 8)

BB+ 1.41|Sempron 2.8|geforce fx5200|1GB DDR|XP home SP2 / prof.

	Rallimen Sieger des 30-EUR-Wettbewerbs	So, März 13, 2005 13:01 Antworten mit Zitat
1000003 < 7 stellige Primzahl 100003 < 6 stellige Primzahl Hier der Code, aber schon wieder etwas schneller! BlitzBasic: [AUSKLAPPEN] [EINKLAPPEN] Global DateiLogPfad$ = \"PrimzahlenLogBuch+.tmp\" Type prim Field zahl End Type ; diese als erstes eingeben, da sie sonst rausfallen durch Function Quer3 p.prim = New prim p\zahl = 3 p.prim = New prim p\zahl = 5 ; Start Time1 = MilliSecs () For i = 1 To 8000000 Step 2 ;nur Ungrade If Quer3 (i) <> 0 Then teilbar = 0 For teiler = 3 To Sqr (i) Step 2 If i Mod teiler = 0 Then teilbar = 1 : Exit Next If teilbar = 0 Then p.prim = New prim p\zahl = i ;Print i + \" / \" + teiler End If End If Next time1 = MilliSecs () - time1 Print time1 / 1000 + \" Sek Dauer 1-8000000\" ; in Datei schreiben dat = WriteFile (DateiLogPfad$) For x.prim = Each prim WriteLine dat,x\zahl Next CloseFile dat ;fertig Print \"fertig\" Print FileSize(DateiLogPfad$) + \" Byte Datei Grösse\" WaitKey() Function Quer3 (A$) If Right (a$,1) = \"5\" Then Return 0 For i = 1 To Len (a$) b% = b% + Mid (a$,i,1) Next Return (b% Mod 3) End Function Sag mir mal deine Zeit!
[BB2D \| BB3D \| BB+]

Rallimen

Sieger des 30-EUR-Wettbewerbs

So, März 13, 2005 13:01
Antworten mit Zitat

1000003 < 7 stellige Primzahl
100003 < 6 stellige Primzahl

Hier der Code, aber schon wieder etwas schneller!
BlitzBasic: [AUSKLAPPEN]

Global DateiLogPfad$ = \"PrimzahlenLogBuch+.tmp\"
Type prim
    Field zahl
End Type
; diese als erstes eingeben, da sie sonst rausfallen durch Function Quer3
p.prim = New prim
p\zahl = 3
p.prim = New prim
p\zahl = 5
; Start
Time1 = MilliSecs ()
    For i = 1 To 8000000 Step 2 ;nur Ungrade
        If Quer3 (i) <> 0 Then
            teilbar = 0
            For teiler = 3 To Sqr (i) Step 2
                If i Mod teiler = 0 Then teilbar = 1 : Exit
            Next
            If teilbar = 0 Then
                p.prim = New prim
                p\zahl = i
                ;Print i + \" / \" + teiler
            End If
        End If
    Next
time1 = MilliSecs () - time1
Print time1 / 1000 + \" Sek Dauer 1-8000000\"
; in Datei schreiben
dat = WriteFile (DateiLogPfad$)
For x.prim = Each prim
    WriteLine dat,x\zahl
Next
CloseFile dat
;fertig
Print \"fertig\"
Print FileSize(DateiLogPfad$) + \" Byte  Datei Grösse\"
WaitKey()

Function Quer3 (A$)
    If Right (a$,1) = \"5\" Then Return 0
    For i = 1 To Len (a$)
        b% = b% + Mid (a$,i,1)
    Next
    Return (b% Mod 3)
End Function

Sag mir mal deine Zeit!

[BB2D | BB3D | BB+]

	dominik	So, März 13, 2005 13:22 Antworten mit Zitat
Da Rallimen ja meinte das es reicht wenn man den teiler bis zur wurzel testet hab ich mal die Zeile: BlitzBasic: [AUSKLAPPEN] [EINKLAPPEN] While i% < Z And primzahl = True in BlitzBasic: [AUSKLAPPEN] [EINKLAPPEN] While i% <= Sqr#(Z) And primzahl = True abgeändert was das ganze extrem beschleunigt! aber stimmen die ergebnisse dann noch?
BB+ 1.41\|Sempron 2.8\|geforce fx5200\|1GB DDR\|XP home SP2 / prof.

dominik

So, März 13, 2005 13:22
Antworten mit Zitat

Da Rallimen ja meinte das es reicht wenn man den teiler bis zur wurzel testet hab ich mal die Zeile:
BlitzBasic: [AUSKLAPPEN]

  While i% < Z And primzahl = True

in
BlitzBasic: [AUSKLAPPEN]

      While i% <= Sqr#(Z) And primzahl = True

abgeändert was das ganze extrem beschleunigt!
aber stimmen die ergebnisse dann noch?

BB+ 1.41|Sempron 2.8|geforce fx5200|1GB DDR|XP home SP2 / prof.

	Mogon	So, März 13, 2005 13:43 Antworten mit Zitat
Ich hab auch irgendwann mal sowas gemacht. Ganz ohne Optimierungen hat der 36 Sekunden für die Primzahlen im Zahlenraum von 1 bis 50000 gebraucht...

Mogon

So, März 13, 2005 13:43
Antworten mit Zitat

Ich hab auch irgendwann mal sowas gemacht. Ganz ohne Optimierungen hat der 36 Sekunden für die Primzahlen im Zahlenraum von 1 bis 50000 gebraucht... Embarassed

	TheShadow Moderator	So, März 13, 2005 13:59 Antworten mit Zitat
wenn du eine primzahl errechnest, dann speichere diese in einer liste... wenn du eine zahl auf primzahl testest, dann probiere erst alle zahlen aus dieser liste.... dadurch ist es schneller
AMD64 3500+ \| GeForce6600GT 128MB \| 1GB DDR \| WinXPsp2

TheShadow

Moderator

So, März 13, 2005 13:59
Antworten mit Zitat

wenn du eine primzahl errechnest, dann speichere diese in einer liste... wenn du eine zahl auf primzahl testest, dann probiere erst alle zahlen aus dieser liste.... dadurch ist es schneller

AMD64 3500+ | GeForce6600GT 128MB | 1GB DDR | WinXPsp2

	dominik	So, März 13, 2005 14:09 Antworten mit Zitat
Rallimen hat Folgendes geschrieben: habs überprüft, und rechnet auch richtig! Allerdings brauchst nur die Ungraden zu testen und das nur rauf bis zur Wurzel der Zahl, denn ab da wiederholt sich alles nur. Wenn die Quersumme durch 3 teilbar ist dann ist es auch keine Primzahl. Wenn du das berücksichtigst dann gehts auch schneller mit der Rechnerrei, das Problem beginnt erst ab Zahlen die größer als Integer 4Byte sind hier noch ein paar Testzahlen: 8999849 8999867 8999897 8999899 8999927 8999957 8999971 8999981 8999993 So bin jetzt auch bis zur 9 Mio gekommen, aber mein prog meint das 8999867 auch eine Primzahlen ist, die du allerdings nicht in deiner Liste hast???? @TheShadow: Sorry aber vewrsteh nicht ganz was du meinst. Klar speichere ich die primzahlen in einer liste in einer datei. aber die zahlen die niedriger sind als die gerade errechnete interessiert mich doch nicht mehr. Die hat doch keine einfluss mehr auf größere.
BB+ 1.41\|Sempron 2.8\|geforce fx5200\|1GB DDR\|XP home SP2 / prof.

dominik

So, März 13, 2005 14:09
Antworten mit Zitat

Rallimen hat Folgendes geschrieben:

So bin jetzt auch bis zur 9 Mio gekommen, aber mein prog meint das 8999867 auch eine Primzahlen ist, die du allerdings nicht in deiner Liste hast????

@TheShadow: Sorry aber vewrsteh nicht ganz was du meinst.
Klar speichere ich die primzahlen in einer liste in einer datei. aber die zahlen die niedriger sind als die gerade errechnete interessiert mich doch nicht mehr. Die hat doch keine einfluss mehr auf größere.

BB+ 1.41|Sempron 2.8|geforce fx5200|1GB DDR|XP home SP2 / prof.

	NetPad	So, März 13, 2005 15:13 Antworten mit Zitat
8999867ist auch eine primzahl

NetPad

So, März 13, 2005 15:13
Antworten mit Zitat

8999867ist auch eine primzahl

	TheShadow Moderator	So, März 13, 2005 15:30 Antworten mit Zitat
sagen wir mal du willst die zahl 6843217 prüfen. so jetzt im schlimmsten fall prüfst du es von 2 bis die hälfte von 6843217. das ist uneffezient und dauert jahre... das wäre etwa diese zeile: FOR teiler = 3 TO SQR (i) STEP 2 (wobei ich mit das mit SQR nicht sicher bin... aber ich denke das wird wohl so stimmen wenn es hier einer sagt) so und nun stell dir vor du hast eine liste mit allen primzahlen bis unter 6843217. Warum benutzt du dann nicht diese liste? (die relativ klein ist) Die Liste soll autom. aus allen zahlen generiert werden die ermittelt wurden und wächst ständig... naja... Zudem. ich hab vor paar Jahren gelesen, dass paar mathematiker eine methode entdeckt haben, mit der man sehr schnell eine zahl testen kann ob diese eine primzahl ist... davon hab ich jedoch nie wieder was gehört...
AMD64 3500+ \| GeForce6600GT 128MB \| 1GB DDR \| WinXPsp2

TheShadow

Moderator

So, März 13, 2005 15:30
Antworten mit Zitat

sagen wir mal du willst die zahl 6843217 prüfen. so jetzt im schlimmsten fall prüfst du es von 2 bis die hälfte von 6843217. das ist uneffezient und dauert jahre...

das wäre etwa diese zeile:
FOR teiler = 3 TO SQR (i) STEP 2

(wobei ich mit das mit SQR nicht sicher bin... aber ich denke das wird wohl so stimmen wenn es hier einer sagt)
so und nun stell dir vor du hast eine liste mit allen primzahlen bis unter 6843217. Warum benutzt du dann nicht diese liste? (die relativ klein ist)

Die Liste soll autom. aus allen zahlen generiert werden die ermittelt wurden und wächst ständig...

naja...

Zudem. ich hab vor paar Jahren gelesen, dass paar mathematiker eine methode entdeckt haben, mit der man sehr schnell eine zahl testen kann ob diese eine primzahl ist... davon hab ich jedoch nie wieder was gehört...

AMD64 3500+ | GeForce6600GT 128MB | 1GB DDR | WinXPsp2

	Rallimen Sieger des 30-EUR-Wettbewerbs	So, März 13, 2005 16:28 Antworten mit Zitat
Zitat: So bin jetzt auch bis zur 9 Mio gekommen, aber mein prog meint das 8999867 auch eine Primzahlen ist, die du allerdings nicht in deiner Liste hast???? Dominik: Wieso steht die Zahl nicht bei dir in der Datei, bei mir ist diese mit drin! Auszug: Zitat: 8999839 8999849 8999867 8999897 8999899 Oder hast du die Schleife geändert?BlitzBasic: [AUSKLAPPEN] [EINKLAPPEN] For i = 1 To 8000000 Step 2 Ganz wichtig! Diese muß mit einer ungraden Zahl beginnen!
[BB2D \| BB3D \| BB+]