Primzahlen

Übersicht BlitzBasic Codearchiv

Gehe zu Seite 1, 2  Weiter

Neue Antwort erstellen

Smily

Betreff: Primzahlen

BeitragDi, Apr 03, 2007 20:51
Antworten mit Zitat
Benutzer-Profile anzeigen
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

hectic

Sieger des IS Talentwettbewerb 2006

BeitragDi, Apr 03, 2007 20:58
Antworten mit Zitat
Benutzer-Profile anzeigen
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

BeitragDi, Apr 03, 2007 21:10
Antworten mit Zitat
Benutzer-Profile anzeigen
Bei mir dauerts 1122 ms. Rechner = Intel Pentium 4 2,8 GH 512 RAM GK 128 MB (mal ne lustige zahl 1122 ^^)

Smily

BeitragDi, Apr 03, 2007 22:04
Antworten mit Zitat
Benutzer-Profile anzeigen
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

BeitragDi, Apr 03, 2007 22:19
Antworten mit Zitat
Benutzer-Profile anzeigen
512 ms Very Happy
cooles teil^^
fllt solltest du noch alles mit 5 am ende rausfischen?
Programmers dont die. They gosub without return...

Triton

BeitragDi, Apr 03, 2007 22:33
Antworten mit Zitat
Benutzer-Profile anzeigen
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. Smile
Coding: silizium-net.de | Portfolio: Triton.ch.vu

FreetimeCoder

BeitragMi, Apr 04, 2007 7:01
Antworten mit Zitat
Benutzer-Profile anzeigen
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

BeitragMi, Apr 04, 2007 11:03
Antworten mit Zitat
Benutzer-Profile anzeigen
Ist es wirklich nicht. Die Zeit ist was anderes.

Denk mal an String-Routinen Smile
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 Laughing
Seit der Earthlings-Diskussion überzeugter Fleisch(fr)esser.
 

E. Urbach

ehemals "Basicprogger"

BeitragMi, Apr 04, 2007 11:18
Antworten mit Zitat
Benutzer-Profile anzeigen
@StepTiger: Es ist unmöglich, es gibt nämlich keine unendlich große Primzahl, lediglich die Menge der Primzahlen ist unendlich groß Wink
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) Wink
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

BeitragMi, Apr 04, 2007 11:26
Antworten mit Zitat
Benutzer-Profile anzeigen
Dann wandel bitte das unendlich in beliebig um Razz
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 Laughing
Seit der Earthlings-Diskussion überzeugter Fleisch(fr)esser.

pixelshooter

BeitragMi, Apr 04, 2007 11:27
Antworten mit Zitat
Benutzer-Profile anzeigen
ich habe es mal in Java umgewandelt (mit div. optimierungen): 60ms. Zwei mathelehrer von uns ham gewettet, wers schneller schafft, glaub ca. 30ms Shocked . Hab deren code hier, aber gedruckt, und der is mir zu lang zum abtippen Cool
>> Musikerstellung, Grafik und Design: http://www.pixelshooter.net.tc

Smily

BeitragMi, Apr 04, 2007 12:41
Antworten mit Zitat
Benutzer-Profile anzeigen
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

BeitragMi, Apr 04, 2007 17:45
Antworten mit Zitat
Benutzer-Profile anzeigen
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. Urbach

ehemals "Basicprogger"

BeitragDo, Apr 05, 2007 9:14
Antworten mit Zitat
Benutzer-Profile anzeigen
@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 Wink
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
 

#Reaper

Newsposter

BeitragDo, Apr 05, 2007 10:14
Antworten mit Zitat
Benutzer-Profile anzeigen
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

Rallimen

Sieger des 30-EUR-Wettbewerbs

BeitragDo, Apr 05, 2007 14:23
Antworten mit Zitat
Benutzer-Profile anzeigen
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

aMul

Sieger des Minimalist Compo 01/13

BeitragDo, Apr 05, 2007 14:44
Antworten mit Zitat
Benutzer-Profile anzeigen
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 Wink
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

Rallimen

Sieger des 30-EUR-Wettbewerbs

BeitragDo, Apr 05, 2007 15:11
Antworten mit Zitat
Benutzer-Profile anzeigen
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

BeitragDo, Apr 05, 2007 15:12
Antworten mit Zitat
Benutzer-Profile anzeigen
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 Laughing
Seit der Earthlings-Diskussion überzeugter Fleisch(fr)esser.

Rallimen

Sieger des 30-EUR-Wettbewerbs

BeitragDo, Apr 05, 2007 15:38
Antworten mit Zitat
Benutzer-Profile anzeigen
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+]

Gehe zu Seite 1, 2  Weiter

Neue Antwort erstellen


Übersicht BlitzBasic Codearchiv

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group