Vorheriges Thema anzeigen :: Nächstes Thema anzeigen |
Autor |
Nachricht |
Random
Anmeldungsdatum: 09.03.2006 Beiträge: 47
|
Verfasst am: 13.03.2008, 22:15 Titel: Primzahlenprogramm |
|
|
Hallo Freunde. Ich hab widermal ein Primzahlenprogramm gebastelt, doch hab ich da ein paar Problemchen:
Das Programm markiert alle ungeraden Mehrfachen einer Zahl bis zu ihrem Quadrat in eine Tabelle. In der Tabelle sind aber auch alle geraden Zahlen gespeichert, welche 50% RAM fressen. Auch werden die teilbaren Zahlen mit einer 1 markiert, statt mit einer boolschen Variable (also nur mit einem Bit). Auch sucht das Programm die Mehrfachen von bereits als teilbar markierten Zahlen. Ich hab da schon ein paar Stunden dran rumgebastelt, doch komme ich einfach nicht weiter; ich müsste wohl nochmals von vorne beginnen, was ich mir aber ersparen möchte. Darum bitte ich euch mir zu helfen, falls das euch keine zu grossen Umstände bereitet. Schonmal vielen Dank.
Hier mal das Hauptprogramm:
Code: |
dim shared as integer feld
feld=10000000
dim atrib(feld)
dim shared as integer x,y,z
x=3:y=3:z=100000
do
if x*y>z then x=3:y=y+2 else x=x+2
if y^2>z then exit do
atrib(x*y)=1
loop
for i=3 to z step 2
if atrib(i)=0 then print i;
next i
sleep
end
|
Hier noch das "fertige" Programm:
http://www.8ung.at/hitech/ps.bas
http://www.8ung.at/hitech/ps.exe |
|
Nach oben |
|
|
volta
Anmeldungsdatum: 04.05.2005 Beiträge: 1875 Wohnort: D59192
|
Verfasst am: 14.03.2008, 00:36 Titel: |
|
|
Hi,
hiermit hatte ich das mal probiert
Code: | Const As UInteger N = 15485863 'bis zu diesem Wert 1.000.000 Primzahlen finden
Dim s As Single
Screen 18
ReDim As Byte Sieb(2 To N)
Dim As Integer i,c,j,delta, sqr_N= Sqr(N)
s= Timer
For j = 4 To N Step 2 'geraden Zahlen
sieb(j) = 1 'keine Primzahl
Next
For j = 3 To sqr_N Step 2
If sieb(j)=0 Then '= Primzahl zB. j=3
delta = 2 * j 'delta = 6
For i = 3 * j To N Step delta '9; 15; 21; 27; 33 ...
sieb(i) = 1 'keine Primzahl
Next
End If
Next
s=Timer-s
c = 0
For i = 2 To N
If sieb(i)=0 Then
'Print i;Chr(9);'Achtung Anzeige dauert lange
c += 1
End If
Next
Print
Print c; " Primzahlen , in ";Left(Str(s),5);" Sek. gefunden!"
Sleep |
_________________ Warnung an Choleriker:
Dieser Beitrag kann Spuren von Ironie & Sarkasmus enthalten.
Zu Risiken & Nebenwirkungen fragen Sie Ihren Therapeuten oder Psychiater. |
|
Nach oben |
|
|
Random
Anmeldungsdatum: 09.03.2006 Beiträge: 47
|
Verfasst am: 14.03.2008, 09:35 Titel: |
|
|
Vielen Dank; das ist ja richtig schnell!! |
|
Nach oben |
|
|
dreael Administrator
Anmeldungsdatum: 10.09.2004 Beiträge: 2507 Wohnort: Hofen SH (Schweiz)
|
Verfasst am: 14.03.2008, 09:49 Titel: |
|
|
Zum Thema Boolean: Einen richtige Boolean-Datentyp besitzt auch FreeBasic bekanntlich nicht, aber im Prinzip lässt sich ein Bit-Array wie folgt realisieren:
Code: | Dim f(0 To 999) As UInteger
' Entspricht Dim f(0 To 31999) As Boolean
' Operation lesen, d.h. f(i)
bit = (f(i Shr 5) Shr (i And 31))And 1
' Bit setzen, d.h. Operation f(i) = 1 bzw. True
f(i Shr 5) Or= 1 Shl (i And 31)
' Bit löschen, d.h. Operation f(i) = 0 bzw. False
f(i Shr 5) And= Not (1 Shl (i And 31)) |
d.h. so lässt sich das RAM für das Sieb des Eratostenes besonders effizient nutzen.
Übrigens praktische Anwendung von mir:
http://www.dreael.ch/Deutsch/Download/Mastermind-Knacker.html
d.h. die C++-Version verwendet dort für die Kombinationenstreichtabelle ebenfalls eine derart bitweise organisierte Tabelle im RAM. _________________ Teste die PC-Sicherheit mit www.sec-check.net |
|
Nach oben |
|
|
Random
Anmeldungsdatum: 09.03.2006 Beiträge: 47
|
Verfasst am: 15.03.2008, 13:17 Titel: |
|
|
Werd ich mal versuchen, danke.
Ich hab jetzt mal zwei Programme geschrieben, welche eine Zahlenreihe mit MOD bis zu einer gewissen Teilergrösse untersucht. Das eine schreibt die Daten erst in ein Arrey, das andere gibt sie direkt aus. Jetzt das verblüffende: die Arrey-Methode, welche ja "einen längeren Weg" macht, braucht nur 6s für alle Primzahlen bis 1000000, die direkte Methode hingegen 13s. Sollte man da nicht alle Variablen immer in ein Arrey schreiben, um ein Programm "etwas" schneller zu machen? Und warum ist diese Methode so viel schneller? Vielen Dank
Arrey:
Programm
Quelltext
Normal:
Programm
Quelltext |
|
Nach oben |
|
|
Random
Anmeldungsdatum: 09.03.2006 Beiträge: 47
|
Verfasst am: 15.03.2008, 21:25 Titel: |
|
|
Hab grad gemerkt, dass diese Methode wohl nur unter gewissen Umständen schneller ist. |
|
Nach oben |
|
|
Heizi
Anmeldungsdatum: 19.01.2005 Beiträge: 309
|
Verfasst am: 16.03.2008, 18:54 Titel: |
|
|
auch ein netter Alghorhytmus:
Code: |
dim pz(1000000) as long
dim co as long
dim co2 as integer
dim primfound as integer
Print "Primzahlen"
pz(0)=2
pz(1)=3
primfound=1
for co= 5 to 1000000 step 2
maxz=sqr(co)
for co2 = 1 to primfound
if co mod pz(co2) = 0 then
'print "co,pz,maxz",co,pz(co2),maxz
'sleep
goto nextco
end if
if pz(co2)> maxz then
exit for
end if
next co2
primfound=primfound+1
pz(primfound)=co
nextco:
next co
print "gefunden ", primfound+1
sleep
for co2 = 0 to primfound
print pz(co2)
sleep
next co2
|
Eine Primzahl ist ja dann nur eine Primzahl wenn man
sie nicht in andere Primzahlenfaktoren zerlegen kann.
Dieser Algo kennt anfangs nur ein paar Primzahlen und
erweitert sich dann selbstständig.
MfG |
|
Nach oben |
|
|
|