Euklidischer Algoritmus und Sieb des Eratosthenes in Java

  • Hallo Kerbonauten, hallo Hobby- und Profiprogrammierer,


    wie ihr an der Überschrift sicherlich erkennen könnt, geht es um ein Problem, das sich mit Java beschäftigt.
    Am Montag segelte für unseren Informatikkurs eine Aufgabe ein. Diese beinhaltet den Euklidischen Algorithmus und das Sieb des Erathostenes als Struktogramm und als Javacode aufzustellen.


    Das Struktogramm für den Euklidischen Algorithmus habe ich von hier (letzte Seite) übernommen. Den Code habe ich mir eher abgeschrieben als verstanden. Er sieht so aus:


    integer a;
    integer b;


    if(b!=0)
    { if (a>b) {a = a-b}
    else b =b-a}
    else (meinStift.schreibeText("Der ggT ist" a);


    (Ein kleiner Kommentar zum letzten Befehl: meinStift. ist ein Objekt aus Sum.kern für BlueJ).


    Ich würde mich freuen, wenn ihr mir sagen könntet, ob der Code stimmt, oder wenn nicht (wovon ich aussgehe :P ), was falsch ist.
    ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------


    Der nächste Punkt ist das Sieb des Eratosthenes.
    Hier ist aus der Sicht der Informatik mein Wissenstand nicht nur unterm Horizont, sondern überhaupt nicht vorhanden!


    Auch hier habe ich das Problem, dass ich ein Struktogramm und den Javacode brauche. Der Artikel hierzu fällt deutlich kürzer aus: Ich habe gar nichts dazu.
    Ich verstehe, wie man das Sieb anwendet, wozu es da ist, aber nicht, wie ich es einem Computer beibringe. Natürlich habe ich mehrere Stunden Google hinter mir, aber die ganzen Codes sind für mich gänzlich UNVERSTÄNDLICH!


    Ich habe bei einem Lehrer, der den Stoff nicht ganz so rüberbringt, dass wir ihn verstehen. Wenn ihr versteht, was ich meine......... Weiterhin kommt dazu, dass ich erst seit diesem Schuljahresanfang überhaupt Informatik habe und wir uns bis jetzt ausschließlich mit BlueJ und der Erweiterung Sum.kern beschäftigt haben (das beinhaltet Vierecke malen und neulich auch Sterne zeichenen [mit ganz wenig rechnen]). Nun flattert diese Aufgabe rein.


    Ich bitte euch nun, könntet ihr mir in meiner Not helfen und das Struktogramm und den Code "zu mir bringen". Bitte beachtet dabei, dass ich erst 10 Klasse bin (wenn auch Gymnasium [in Brandenburg]).



    Ich freue mich sehr, wenn ihr mir helfen könntet!


    Felix

  • Hi
    Ich persönlich programmiere kein Java. Nur etwas Python für die Blender Game Engine
    Daum kann ich dir deine Erste frage nicht beantworten. Kann dir aber vielleicht einen Denkanstöß geben:
    - Auf wikipedia ist eine "während" bzw. "until" Schleife. Hast du die auch in deinen Code eingebaut?


    ###-----###-----###-----###-----###-----###-----###-----###-----###-----###-----###-----###-----###-----###-----###-----###-----###


    Bei zweitem kann ich dir vielleicht helfen.


    Ich hab den Sieb des Erathostenesgerade mal ausprobiert.


    Ist eigentlich ganz Simpel:


    Du brauchst zwei Listen


    Liste A und Liste B


    In Liste A schreibst du alle zahlen von 2 bis wohin dein Algorithmus halt gehen soll.
    Ganz wichtig. In der Liste darf keine 0 Stehen, weil du später durch die Teilen würdest.
    Und keine 1, weil du die Vielfachen von jeder Primzahl in der Liste raus werfen wirst... Jede Zahl ist ein Vielfaches von 1. Also währe die liste sofort leer :D


    OK:
    Du nimmst dir Liste A und steckst die erste Zahl in Liste B.
    Jetzt überprüfst du für jede Zahl in Liste A. Ob sie ein vielfaches der letzten Zahl aus Liste B ist.
    (dazu einfach jede Zahl aus Liste A durch die Zahl aus Liste B teilen und überprüfen ob das Ergebnis gerundet das Selbe ist wie ungerundet)
    Wenn Ja. Wirfst du dieses Vielfache aus Liste A heraus. Wenn Nein, machst du garnichts.


    Wenn das einmal komplett durchgelaufen ist hast du deine erste Primzahl => 2
    Und alle Vielfachen von 2 (und die 2 selbst) aus der Liste A heraus geworfen.


    Jetzt kannst du das endlos weiter wiederholen lassen.


    du bist fertig sobald dir deine Console einen Error ausspuckt, dann hast du alle Primzahlen gefunden.


    beim zweiten Durchlauf wird die 3 die erste Zahl in Liste A sein.
    Die wird in Liste B gesteckt und ist jetzt die letzte Zahl in Liste B.



    So sieht das ganze bei mir in der Blender Game Engine, also in Phyton aus:



    Ja ich weiß, Ich hätte das auch mit einer for oder until schleife machen können.
    Ich wollte dem Script aber bei jeder Iteration zugucken ;)



    Ich bin übrigens auch kein "Profi" oder sowas.
    ich mach das ganze hobbymäßig nebenbei ...
    Könnte also alles Quatsch sein was ich hier hin geschrieben habe :D

  • Danke für deine Bemühungen Nibooss,


    das Problem hat sich gerade von selbst gelöst. Ich hatte heute ein "anregendes" Gespräch mit meinem Lehrer, wir sollen jetzt alles nur aus dem Internet ziehen und sogut wie es geht verstehen, d.h. ich werde es wahrscheinlich nicht verstehen. :P
    Trotzdem nochmal danke Nibooss!
    Aber trotzalledem kann ich mich als einer der nennen, die überhaupt verstanden haben, was die Algorithmen bedeuten (es ist sehr lustig in Biologie den Euklidischen Algorithmus und das Sieb des Eratosthenes zu erklären) :crylaugh:


    Nochmal danke


    Felix