Primzahlen
Übersicht

![]() |
SmilyBetreff: Primzahlen |
![]() Antworten mit Zitat ![]() |
---|---|---|
heyho,
ich habe mich mal an einem Programm versucht, was Primzahlen so schnell wie möglich ausrechnet: Code: [AUSKLAPPEN] p = 1000000
Dim Zahl(p) Zahl(0) = 1 Zahl(1) = 1 st = MilliSecs() For z = 2 To p If zahl(z) = 0 Then a = z Repeat a = a + z If a <= p zahl(a) = 1 Until a => p - z End if Next et = MilliSecs() Print "Fertig!" Print "Benötigte Zeit: " + (et-st) + " ms" fileout = WriteFile("Prim.txt") Print "Primzahlen Speichern." For x = 0 To p-1 If not zahl(x) Then WriteLine fileout, x Next Das Programm errechnet auf meinem Rechner alle Primzahlen bis 1.000.000 in nur 280 Millisekunden. Damit ist es die Schnellste mir bekannte Methode Primzahlen zu errechnen. Wer einen noch schnelleren Algorhytmus hat kann ihn gerne Posten, ich bin für weitere Methoden der Berrechnung immer offen. Gruß, Smily0412 |
||
Lesestoff:
gegen Softwarepatente | Netzzensur | brain.exe | Unabhängigkeitserklärung des Internets "Wir müssen die Rechte der Andersdenkenden selbst dann beachten, wenn sie Idioten oder schädlich sind. Wir müssen aufpassen. Wachsamkeit ist der Preis der Freiheit --- Keine Zensur!" stummi.org |
- Zuletzt bearbeitet von Smily am Mi, Apr 04, 2007 12:50, insgesamt 3-mal bearbeitet
![]() |
hecticSieger des IS Talentwettbewerb 2006 |
![]() Antworten mit Zitat ![]() |
---|---|---|
Die Berechnungen sind aber falsch...
4, 6, 8, 9, 10, 12, 14, 15, 16, ... So währen sie richtig... 2, 3, 5, 7, 11, 13, 17, ... edit1: Sehe grad. Du könntest es eventuell mit einer Negativliste lösen. |
||
Darkbyte |
![]() Antworten mit Zitat ![]() |
|
---|---|---|
Bei mir dauerts 1122 ms. Rechner = Intel Pentium 4 2,8 GH 512 RAM GK 128 MB (mal ne lustige zahl 1122 ^^) | ||
![]() |
Smily |
![]() Antworten mit Zitat ![]() |
---|---|---|
hectic hat Folgendes geschrieben: Die Berechnungen sind aber falsch...
4, 6, 8, 9, 10, 12, 14, 15, 16, ... So währen sie richtig... 2, 3, 5, 7, 11, 13, 17, ... edit1: Sehe grad. Du könntest es eventuell mit einer Negativliste lösen. ups sry ^^ Hatte versehentlich einen Operator falsch gesetzt. Ich hatte für einen kleinen Test eine änderung vorgenommen und den Code dann nicht wieder zurück-geändert. Habs jetzt Korrigiert |
||
Lesestoff:
gegen Softwarepatente | Netzzensur | brain.exe | Unabhängigkeitserklärung des Internets "Wir müssen die Rechte der Andersdenkenden selbst dann beachten, wenn sie Idioten oder schädlich sind. Wir müssen aufpassen. Wachsamkeit ist der Preis der Freiheit --- Keine Zensur!" stummi.org |
Schnuff |
![]() Antworten mit Zitat ![]() |
|
---|---|---|
512 ms ![]() cooles teil^^ fllt solltest du noch alles mit 5 am ende rausfischen? |
||
Programmers dont die. They gosub without return... |
![]() |
Triton |
![]() Antworten mit Zitat ![]() |
---|---|---|
135 ms bei mir. Nicht schlecht. Sieht mir ganz nach einer Umsetzung des Siebes des Eratosthenes aus. Das ist zwar für kleine Zahlen ganz gut, bei größeren aber unbrauchbar.
Versuch doch mal das Programm so zu erweitern, dass es unendlich große Primzahlen ermitteln kann. ![]() |
||
Coding: silizium-net.de | Portfolio: Triton.ch.vu |
![]() |
FreetimeCoder |
![]() Antworten mit Zitat ![]() |
---|---|---|
Zitat: Versuch doch mal das Programm so zu erweitern, dass es unendlich große Primzahlen ermitteln kann.
Jaja xD ist ja auch gar nicht so schwer^^ |
||
"Wir haben keine Chance, aber wir werden sie nutzen!"
Projekte: Dexterity Ball (100%) Aquatic Atmosfear (22 % ca 4700 Zeilen) eingefrohren mangels OOP Fähigkeiten von Blitz (ehemals Uboot) PC: Intel D 3 GHz | NVidiaGforce 6700 256 Mb | 1024 Mb DDR RAM 400 Mhz | 2x160 GB S-ATA |
![]() |
StepTiger |
![]() Antworten mit Zitat ![]() |
---|---|---|
Ist es wirklich nicht. Die Zeit ist was anderes.
Denk mal an String-Routinen ![]() |
||
Noch gestern standen wir am Abgrund, doch heute sind wir schon einen Schritt weiter.
Computer: AMD Sempron 3000+; ATI Radeon 9800 Pro; 512 MB DDR RAM 400Mhz; Asus E7N8X-E Deluxe; Samsung 200GB HD 5.4ns acces t Gewinner: BP Code Compo #2 Π=3.141592653589793238...<--- und das aus dem kopf ![]() Seit der Earthlings-Diskussion überzeugter Fleisch(fr)esser. |
E. Urbachehemals "Basicprogger" |
![]() Antworten mit Zitat ![]() |
|
---|---|---|
@StepTiger: Es ist unmöglich, es gibt nämlich keine unendlich große Primzahl, lediglich die Menge der Primzahlen ist unendlich groß ![]() siehe: Zitat: Versuch doch mal das Programm so zu erweitern, dass es unendlich große Primzahlen ermitteln kann.
Ontopic: Nicht schlecht, B3D ohne Debug: 97 ms Kannst es ja mal in C/C++ umwandeln, dann hast du sicherlich eine höhere Geschwindigkeit (wenn du's richtig umsetzt) ![]() |
||
The box said, "Requires Windows XP or better", so I installed Ubuntu | Linux is NOT Windows
Flua :: Profiler für BB und BMax :: Partikel-Engine für BMax :: Lyphia-Projekt Quellcode (BMax) :: Automatische Parallelisierung :: Meine Musik |
![]() |
StepTiger |
![]() Antworten mit Zitat ![]() |
---|---|---|
Dann wandel bitte das unendlich in beliebig um ![]() |
||
Noch gestern standen wir am Abgrund, doch heute sind wir schon einen Schritt weiter.
Computer: AMD Sempron 3000+; ATI Radeon 9800 Pro; 512 MB DDR RAM 400Mhz; Asus E7N8X-E Deluxe; Samsung 200GB HD 5.4ns acces t Gewinner: BP Code Compo #2 Π=3.141592653589793238...<--- und das aus dem kopf ![]() Seit der Earthlings-Diskussion überzeugter Fleisch(fr)esser. |
![]() |
pixelshooter |
![]() Antworten mit Zitat ![]() |
---|---|---|
ich habe es mal in Java umgewandelt (mit div. optimierungen): 60ms. Zwei mathelehrer von uns ham gewettet, wers schneller schafft, glaub ca. 30ms ![]() ![]() |
||
>> Musikerstellung, Grafik und Design: http://www.pixelshooter.net.tc |
![]() |
Smily |
![]() Antworten mit Zitat ![]() |
---|---|---|
Letztendlich hängt die Geschwindigkeit ja zum Großteil vom Rechenprinzip ab.
Diese methode lässt sich imho leider nicht so erweitern, dass es beliebig viele Primzahlen ausrechnen kann. Ich hab mal versucht statt ein dim ein Type zu verwenden, wo nur die Primzahlen gespeichert werden. Aber aus mir unerfindlichen gründen ist der Code jetzt total langsam ^^: Code: [AUSKLAPPEN] Type Primzahl
Field wert End Type Local Prim.primzahl st = MilliSecs() For z = 2 To 1000000 If Not (z Mod 10000) Print z n = 0 For Prim = Each Primzahl If Not (z Mod prim\wert) Then n = 1 Next If Not n prim = New primzahl prim\wert = z End if Next et = MilliSecs() Print et-st Edit: @Schnuff: Genau das ist ja eigentlich das Prinzip meines Programms |
||
Lesestoff:
gegen Softwarepatente | Netzzensur | brain.exe | Unabhängigkeitserklärung des Internets "Wir müssen die Rechte der Andersdenkenden selbst dann beachten, wenn sie Idioten oder schädlich sind. Wir müssen aufpassen. Wachsamkeit ist der Preis der Freiheit --- Keine Zensur!" stummi.org |
![]() |
FireballFlame |
![]() Antworten mit Zitat ![]() |
---|---|---|
Bei mir sinds 98ms ohne Debugger. Nich schlecht.
Types sind nunmal langsamer als Dims ^^ |
||
PC: Intel Core i7 @ 4x2.93GHz | 6 GB RAM | Nvidia GeForce GT 440 | Desktop 2x1280x1024px | Windows 7 Professional 64bit
Laptop: Intel Core i7 @ 4x2.00GHz | 8 GB RAM | Nvidia GeForce GT 540M | Desktop 1366x768px | Windows 7 Home Premium 64bit |
E. Urbachehemals "Basicprogger" |
![]() Antworten mit Zitat ![]() |
|
---|---|---|
@Smily0412 & FireballFlame:
Ich vermute mal, dass das Keyword "New" hier das Problem ist, weil ständig Speicher angefordert wird, was selbstverständlich sehr langsam ist. Zitat: Letztendlich hängt die Geschwindigkeit ja zum Großteil vom Rechenprinzip ab.
Stimmt schon, ändert aber trotzdem nichts daran, das C/C++ Compiler bessere Optimierungen durchführen (unwichtiges auslassen) und besseren Assembler-Code als Blitz3D erzeugen ![]() Zitat: Diese methode lässt sich imho leider nicht so erweitern, dass es beliebig viele Primzahlen ausrechnen kann.
Da man in fast jeder Programmiersprache Arrays dynamisch erstellen kann, geht das eigentlich ganz gut, es muss bloß vor Schleifenanfang bekannt sein, bis zu welcher Zahl er rechnet. Eine vollkommen dynamische Größe wäre in der Tat nicht möglich, wie du schon gesagt hast (aus Performance-Gründen). Zitat: Zwei mathelehrer von uns ham gewettet, wers schneller schafft, glaub ca. 30ms
30 ms in Java? Das will ich sehen. Scan den Code doch ein und lass 'ne OCR-Texterkennungssoftware drüber laufen, die Fehler kannst du ja nachher korrigieren. |
||
The box said, "Requires Windows XP or better", so I installed Ubuntu | Linux is NOT Windows
Flua :: Profiler für BB und BMax :: Partikel-Engine für BMax :: Lyphia-Projekt Quellcode (BMax) :: Automatische Parallelisierung :: Meine Musik |
#ReaperNewsposter |
![]() Antworten mit Zitat ![]() |
|
---|---|---|
Basicprogger hat Folgendes geschrieben: 30 ms in Java? Das will ich sehen. Scan den Code doch ein und lass 'ne OCR-Texterkennungssoftware drüber laufen, die Fehler kannst du ja nachher korrigieren. Ich wundere mich da ebenfalls... Ist Java etwa doch schneller, als ich bisher dachte?! Oder ist nur die Rechenmethode so extrem gut?^^ *wart* |
||
AMD Athlon 64 3500+, ATI AX800 Pro/TD, 2048 MB DRR 400 von Infineon, ♥RIP♥ (2005 - Juli 2015 -> sic!)
Blitz3D, BlitzMax, MaxGUI, Monkey X; Win7 |
![]() |
RallimenSieger des 30-EUR-Wettbewerbs |
![]() Antworten mit Zitat ![]() |
---|---|---|
Hallo, habe mal mein Algo der fast genauso funktioniert wie von Smily0412 und auch gleich schnell umgebaut auf eine Bank.
Das das mit einer Bank schneller geht ist ja logisch, da ich nur ein Byte speicher anstatt 4 Byte beim Array. Diese braucht nur 1/3 der Zeit! Code: [AUSKLAPPEN] Print "HighSpeed Primzahlen Ermittler "
Print "" Print "" BisZahl = 1000000;Input ("Primzahlen bis : ") ; Bank = CreateBank(BisZahl+1) Time1 = MilliSecs (); Zeit Start t2 = 2 ;primzahlen ermitteln For t1 = 2 To BisZahl If PeekByte (Bank,t1) = 0 Then t2 = t1 t2 = t2 + t1 While t2 <= BisZahl PokeByte (Bank,t2,1) t2 = t2 + t1 Wend End If Next Time1 = MilliSecs () - time1; Zeit Ende ;PrimZahlen Speichern Dat = WriteFile ("Primzahlen bis " + BisZahl + " ralli.txt") For t1 = 2 To BisZahl If PeekByte (Bank,t1) = 0 Then WriteLine dat,t1 a = a + 1 End If Next CloseFile Dat Print "In "+time1 + " Millisekunden "+ a+" ermittelt!" Print "" Print "by Rallimen" Print "Bye.." WaitKey |
||
[BB2D | BB3D | BB+]
|
- Zuletzt bearbeitet von Rallimen am Do, Apr 05, 2007 15:13, insgesamt 2-mal bearbeitet
![]() |
aMulSieger des Minimalist Compo 01/13 |
![]() Antworten mit Zitat ![]() |
---|---|---|
Von den etlichen "Offset out of range"-Fehlern mal abgesehen wirklich gut.
Hier die korrigierten Zeilen, damit der Fehler nicht mehr auftritt: Code: [AUSKLAPPEN] ; .....
Bank = CreateBank(BisZahl+1) ; +1 dazu Time1 = MilliSecs () t2 = 2 For t1 = 2 To BisZahl ; +1 weg ; ..... Denn auch Banks liest man von 0 bis 99 aus, nicht von 1 bis 100 ![]() |
||
Panic Pong - ultimate action mashup of Pong and Breakout <= aktives Spiele-Projekt, Downloads mit vielen bunten Farben!
advASCIIdraw - the advanced ASCII art program <= aktives nicht-Spiele-Projekt, must-have für ASCII/roguelike/dungeon-crawler fans! Alter BB-Kram: ThroughTheAsteroidBelt - mit Quelltext! | RGB-Palette in 32²-Textur / Farbige Beleuchtung mit Dot3 | Stereoskopie in Blitz3D | Teleport-Animation Screensaver |
![]() |
RallimenSieger des 30-EUR-Wettbewerbs |
![]() Antworten mit Zitat ![]() |
---|---|---|
Du hast natürlich recht, habs an der falschen Stelle weggemacht.
Blitz nörgelt nur im Debug Modus deswegen ist es nicht aufgefallen. Werd es oben edieren |
||
[BB2D | BB3D | BB+]
|
![]() |
StepTiger |
![]() Antworten mit Zitat ![]() |
---|---|---|
ist bei mir gerade mal ein Unterschied von 30ms.
Das oben: 158ms Das unten: 128ms |
||
Noch gestern standen wir am Abgrund, doch heute sind wir schon einen Schritt weiter.
Computer: AMD Sempron 3000+; ATI Radeon 9800 Pro; 512 MB DDR RAM 400Mhz; Asus E7N8X-E Deluxe; Samsung 200GB HD 5.4ns acces t Gewinner: BP Code Compo #2 Π=3.141592653589793238...<--- und das aus dem kopf ![]() Seit der Earthlings-Diskussion überzeugter Fleisch(fr)esser. |
![]() |
RallimenSieger des 30-EUR-Wettbewerbs |
![]() Antworten mit Zitat ![]() |
---|---|---|
bei mir sind es 158 zu 51 mit BB2D
Und bei B+ schwankt es kurioserweise stark zwischen 30 -90 bei BB3D zwischen 40 und 100 |
||
[BB2D | BB3D | BB+]
|
Übersicht


Powered by phpBB © 2001 - 2006, phpBB Group