Sieb des Erathostenes - DeLuxe-Version

Antworten
Benutzeravatar
ibi
Dr. h.c.
Beiträge: 443
Registriert: 12.10.2006, 20:34
Wohnort: Kagran / Donaustadt

Sieb des Erathostenes - DeLuxe-Version

Beitrag von ibi »

Da der Sieb des Erathostenes gerade Übungsaufgabe war, stelle ich meine (etwas kranke) Version rein, die man besser nicht abgeben sollte. ;)

Code: Alles auswählen

#include <stdio.h>

int main()
{
const int IntBits = sizeof(int) * 8;
int Zahl;
int i;
int j=0;

printf("\nBitte geben Sie eine Zahl ein!\n");
scanf("%i", &Zahl);
printf("Primzahlen von 2 bis %i:\n\n", Zahl);

unsigned int *Sieb;
Sieb = (unsigned int *) malloc(((Zahl) / IntBits + 1) * sizeof(int));

for (i=0; i <= Zahl / IntBits; i++) Sieb[i]=0;

for (i=2; i <= Zahl; i++)
{       if ((Sieb[i / IntBits] & (1<<(i % IntBits))) == 0)
        {       printf("%i, ", i);
                for (j=i; j<=Zahl; j+=i) Sieb[j / IntBits] |= (1 << (j % IntBits));
        }
}
printf("\n");
return 0;
}
Mal sehn obs wer versteht ... ;)

Benutzeravatar
theo
Beiträge: 39
Registriert: 11.10.2006, 13:54
Wohnort: Wien / Höchst
Kontaktdaten:

Beitrag von theo »

Wenn ich das Richtig versteh gibt diese Filter alle Primzahlen bis zur eingegebenen Zahl aus.

Du allokierst dir so viele Bits wie du Zahlen hast und dieser Bitstrom ist dein Sieb.
Dann gehst du ihn durch und jedesmal wenn du eine 0 findest gibst du die Zahl aus und setzt dann alle Vielfachen von dieser Zahl aus dem Bitstrom auf 1.

Hübsch mit Bitoperationen gemacht.

PS: Müsstest du am Schluss nicht noch den Speicher freigeben oder wird das durchs "return" erledigt.
grün ist gelber als blau

Benutzeravatar
ibi
Dr. h.c.
Beiträge: 443
Registriert: 12.10.2006, 20:34
Wohnort: Kagran / Donaustadt

Beitrag von ibi »

Ja, genau. Mir war voriges Jahr zu fad und für jedes Feld einen Integer zu verwenden war irgendwie Verschwendung. Also war Wühlen in der Dokumentation angesagt.
theo hat geschrieben:PS: Müsstest du am Schluss nicht noch den Speicher freigeben oder wird das durchs "return" erledigt.
Das wird durch "return" erledigt, aber sauberer wärs, wenn man free(Sieb) verwendet. Das hab ich damals vergessen.
In Dat II hat die free-Funktion aber öfter einmal aus mir unerfindlichen Gründen segmentation-faults geliefert, weshalb ich sie weggelassen habe. In rekursiven Funktionen sollte man das aber auf keinen Fall machen.
Vielleicht liegts auch daran, daß ich #include <stdlib.h> vergessen hab und der Compiler daher das falsche free() verwendet hat. Das hab ich in diesem Programm auch vergessen (malloc benötigt stdlib.h) *shrug*

Benutzeravatar
theo
Beiträge: 39
Registriert: 11.10.2006, 13:54
Wohnort: Wien / Höchst
Kontaktdaten:

Beitrag von theo »

Ist bei mir auch schon einige Jahre her, dass ich was in C programmiert hab. Geschweige denn, die Verwendung von Bitoperationen. (Ich galube "|=" ist jetzt mein Lieblinsoperator)
grün ist gelber als blau

Benutzeravatar
ibi
Dr. h.c.
Beiträge: 443
Registriert: 12.10.2006, 20:34
Wohnort: Kagran / Donaustadt

Beitrag von ibi »

|= schaut irgendwie stylisch aus. ;)
Ich hab voriges Jahr Datenverarbeitung gehabt und dementsprechend viel C programmiert. Im nächsten Semester (Dat II) macht man dann auch FORTRAN, was einigen besser gefällt, aber ich hab dann doch alles in C programmiert.
FORTRAN find ich irgendwie eingeschränkt, man hat (zumindest bei F77) keine Pointer und keine dynamischen Variablen. Ziemlich unflexibel das ganze.
Die Syntax nervt mich auch (Befehl darf erst in der 7. Spalte beginnen, die ersten sechs Spalten sind für Sonderbefehle reserviert, und Ausgabe und Schleifen find ich auch komisch).
Tja, nächstes Semester darf ich mir dann wohl wieder FORTRAN-Quelltexte durchlesen (aber wenigstens muß ich sie nicht selbst schreiben).

Jetzt darf ich mir für den 3. Teil von Datenverarbeitung Python anschaun. Die Sprache kann zwar einiges, ist vom Syntax her aber widerlich.

Benutzeravatar
Gregor
Beiträge: 69
Registriert: 09.10.2006, 16:32

Beitrag von Gregor »

Warum denn widerlich? Hab mir Python einmal kurz angesehen - angenehm minimalistisch. Verwende einen Python-Interpreter als programmierbaren Taschenrechne für kleinere Sachen. :D

Ciao, G

Benutzeravatar
ibi
Dr. h.c.
Beiträge: 443
Registriert: 12.10.2006, 20:34
Wohnort: Kagran / Donaustadt

Beitrag von ibi »

Mich stört hauptsächlich, daß Blöcke nicht sauber abgeschlossen werden.
Blöcke enden dort, wo man nicht mehr so weit einrückt. Man sieht also nicht auf einem Blick, wie viele Blöcke auf einmal geschlossen werden. Und sobald jemand TAB zum Einrücken verwendet (was einige Editoren machen) wirds chaotisch.

Das zweite ist, daß Variablen nicht deklariert werden.

tsp
Beiträge: 3
Registriert: 22.11.2006, 21:11
Wohnort: Wien
Kontaktdaten:

Beitrag von tsp »

ibi hat geschrieben:In Dat II hat die free-Funktion aber öfter einmal aus mir unerfindlichen Gründen segmentation-faults geliefert, weshalb ich sie weggelassen habe.
Mir fallen eigentlich nur drei Gründe ein warum free einen Segfault hervorrufen könnt:
I) Der Datenblock steht nicht mehr unter der Verwaltung von malloc bzw. man hat vorher mit munmap einen Speicherbereich auf dem Heap ausgeblendet (bzw. mit mprotect die Access Rights geändert) hat.

II) Man hat mit Hilfe der Array Indizierung auf Bereiche außerhalb des mit malloc reservierten Blocks geschrieben - da malloc weitere Informationen vor bzw. nach (Implementierungsspezifisch) dem Datenblock sichert kann's passieren das er dabei auch "beleidigt" ist

III) Gab auch in irgendeiner libc mal eine free Implementierung die bei der Übergabe von null (d.h. free(0)) einen Segfault ausgelöst hat weil free versucht hat auf die Guard Page zuzugreifen.



PS.: Finde C is eigentlich eine "grausliche" Sprache ... (sind so Kleinigkeiten wie Notwendigkeit von Typecasts, das Problem das Overflows bei Rechenoperationen nur umständlich feststellbar sind, etc.)

Benutzeravatar
ibi
Dr. h.c.
Beiträge: 443
Registriert: 12.10.2006, 20:34
Wohnort: Kagran / Donaustadt

Beitrag von ibi »

tsp hat geschrieben:II) Man hat mit Hilfe der Array Indizierung auf Bereiche außerhalb des mit malloc reservierten Blocks geschrieben - da malloc weitere Informationen vor bzw. nach (Implementierungsspezifisch) dem Datenblock sichert kann's passieren das er dabei auch "beleidigt" ist
DAS kann sehr gut sein.
In Dat2 war ich froh, wenn das Programm einmal schönen Output geliefert hat. Ob eine Schleife jetzt bis i-1, i oder i+1 geht waren nebensächliche Details. ;)
Vor allem bei theoretisch mehrdimensionalen Arrays (die ich in eine Dimension gepackt habe) kann da leicht was zerstört worden sein.
tsp hat geschrieben:PS.: Finde C is eigentlich eine "grausliche" Sprache ... (sind so Kleinigkeiten wie Notwendigkeit von Typecasts, das Problem das Overflows bei Rechenoperationen nur umständlich feststellbar sind, etc.)
Das ist zwar etwas unhandlich, aber wenigstens hat man Kontrolle über die Datentypen.
Da gibts Sprachen, die ich um einiges grauslicher finde.

tsp
Beiträge: 3
Registriert: 22.11.2006, 21:11
Wohnort: Wien
Kontaktdaten:

Beitrag von tsp »

Bzgl. den Datentypen ... ich find's halt nur lästig das meine Progs. dann alle zu (leicht übertrieben geschätzt) 2/3 aus Typecasts bestehen ...



Da fällt mir (etwas OT) ein ... kennt irgendwer eine Möglichkeit innerhalb der Source zu bestimmen welche Funktionen von einem Shared Object exportiert werden? (ähnlich NASM's IMPORT / EXPORT Direktiven) (gcc exportiert ja standardmäßig alles was in den Sourcefiles nicht als static (d.h. als global) definiert wurde) ...

Antworten

Zurück zu „Datenverarbeitung für Physiker I“