Sieb des Eratosthenes

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Sieb des Eratosthenes

    Moin Moin

    So nachdem ich mich mehr oder minder hierhin verirrt habe, poste ich gleich mal ein kleines "sinnfreies" Programm mit dem man ein paar Primzahlen ausrechnen kann.

    Das ganze ist natürlich sehr einfach, läuft recht schnell durch und das einzigste, was man vielleicht dabei lernen kann, ist wie man for-Schleifen benutzt.

    Das ganze wurde auch noch etwas beschleunigt, da ich alle geraden Zahlen gleich "ausgeschlossenen" habe.

    Quellcode

    1. public class Prim {
    2. private boolean[] prim;
    4. public Prim(){
    5. prim = new boolean[61870716];
    6. //prim = new boolean[268435455];
    8. init();
    9. }
    11. public Prim(int anz){
    12. prim = new boolean[anz];
    14. init();
    15. }
    17. public void init(){
    18. for(int i = 0; i < prim.length; i++){
    19. prim[i] = true;
    20. }
    21. }
    23. public boolean[] process(){
    24. int zahl = 0;
    25. int wurzel = (int) Math.sqrt(prim.length);
    27. for(int i = 0; i < wurzel; i++){
    28. if(prim[i]){
    29. zahl = 2 * i + 3;
    31. for(int j = (i + zahl); j < prim.length; j += zahl){
    32. prim[j] = false;
    33. }
    34. }
    35. }
    36. return prim;
    37. }
    38. }
    Alles anzeigen


    Vielleicht hat ja jemand noch etwas lust mit mir drüber zu Diskutieren, was man noch so verbessern kann (und ja da gibt es schon einiges)

    mfg
    cr4ch

  • lol - sowas hab ich schonmal im Cpp-Teil gepostet ...

    also im Prinzip legt man ja ein ziemlich langes Array aus bool'schen Werten an nich ?
    Erste Optimierungsmöglichkeit ist, man prüft nicht ganz bis zum Ende, sondern
    nur bis zur Hälfte oder Krasser nur bis zum Drittel, denn jede Zahl, die danach
    auftaucht und KEINE Primzahl wäre, hätte als Teiler mindestens noch ne 2 oder
    ne 3 bis N/3 wäre eben alles drin, man stößt dann nur bei sehr kleinen Werten auf paar Probleme, die man abfangen muss, meiner Erfahrung nach sollte man N größer als 3*3 wählen, da sich das Prinzip sonst von selbst abschiesst ;)

    Jo und dann könnte man auch noch "nur" die Hälfte aller natürlichen Zahlen speichern oder gar zwei Drittel, wobei man wieder bei der 2 und der 3 aufpassen muss, das hat mir dann aber für das simple Programm zu weit geführt, eigentlich gings ja ganz schnell, nur die Ausgabe war lahm - jede Primzahl als HEX, OCT, DEZ oder BIN auszugeben, war aber nen interessantes 30-Minuten-Projekt ;)

  • Hehe scheinst dir ja ein paar "interessante" Gedanken darum gemacht zu haben.
    Wie du richtig festgestellt hast, ist die ausgabe etwas langsam. Um ca. 10700 Primzahlen in ne Datenbank zu schreiben, brauche ich etwas mehr als 6 Minuten.

    Jetzt mach dir mal ein paar gedanken, wie du z.B. alle Primzahlen von 3 - 130.000.000 errechnen kannst, oder was man macht, wenn dir Primzahlen größen Integer.MAX_VALUE werden.