Primzahl bis n

[ocsme]

Ich hab 2 kleine Fragen.
Würde sehr gerne diesen Code aufbessern.

int n = 20;
        boolean prim;
       
        for(int i=2; i<=n;i++)
        {
            prim = true;
            for(int teiler=2;prim&&teiler<i;teiler++)
            {
                if(i%teiler==0)
                    prim=false;
            }
            if(prim)
                System.out.println(i);

Das ganze läuft! Doch ich würde sehr gerne nicht immer durch die 2 Schleife laufen müssen. Deswegen würde ich sehr gerne die ersten Primzahlen zwischen speichern und dann gegen die Zahl i prüfen. Die Zahl i läuft gegen unser n. Damit wären "unnötige" Abfragen wie die vielfachen von 2,3,5,etc. <- Primzahlen weg =)
Geht das nur mit Kontrollstrukturen oder nur mit einem Array? So weit sind wir nicht

und zweitens wieso kann man denn sqrt(n) nehmen? in meinem Fall bei n=20 kommt bei sqrt(n) = 4 raus somit hätte ich ja nur 2,3 als Primzahl und es würden alle anderen Primzahlen ignoriert werden :-(

LG

 

[JStein52]

Hast du dir mal das Sieb des Eratosthenes angeschaut: http://public.beuth-hochschule.de/~solymosi/lehre/eratosthenes/Sieb.html Da steht alles

 

[ocsme]

vielen vielen Lieben Dank
Aber wie schon gesagt Arrays hatten wir noch nicht! und die muss man dann ja nutzen!
Dann funktioniert das auch genauso wie ich es mir gedacht habe.

Jetzt nur noch die Frage wieso sollte ich die obere Schranke n auf sqrt(n) setzen :-O kann mir das jemand mal genau erklären? Denn wie schon gesagt gibt das für mich wenig sinn wenn ich 2-20 Primzahlen suche und er bei n=20 sqrt = 4 macht
LG

 

[JStein52]

Aus Wikipedia:
Zunächst werden alle Zahlen 2, 3, 4,… bis zu einem frei wählbaren Maximalwert S aufgeschrieben. Die zunächst unmarkierten Zahlen sind potentielle Primzahlen. Die kleinste unmarkierte Zahl ist immer eine Primzahl. Nachdem eine Primzahl gefunden wurde, werden alle Vielfachen dieser Primzahl als zusammengesetzt markiert. Man bestimmt die nächstgrößere nicht markierte Zahl. Da sie kein Vielfaches von Zahlen kleiner als sie selbst ist (sonst wäre sie markiert worden), kann sie nur durch eins und sich selbst teilbar sein. Folglich muss es sich um eine Primzahl handeln. Diese wird dementsprechend als Primzahl ausgegeben. Man streicht wieder alle Vielfachen und führt das Verfahren fort, bis man am Ende der Liste angekommen ist. Im Verlauf des Verfahrens werden alle Primzahlen ausgegeben.

Da mindestens ein Primfaktor einer zusammengesetzten Zahl immer kleiner gleich der Wurzel der Zahl sein muss, ist es ausreichend, nur die Vielfachen von Zahlen zu streichen, die kleiner oder gleich der Wurzel der Schranke S sind.

Ebenso genügt es beim Streichen der Vielfachen, mit dem Quadrat der Primzahl zu beginnen, da alle kleineren Vielfachen bereits markiert sind.

 

[JStein52]

Und dieses erwähnte streichen von unmarkierten Zahlen (im Code des vorherigen Links entspricht das true oder false setzen) lässt sich natürlich nur durchführen wenn man irgendeine Art von Array benutzen kann/darf. Sonst geht diese Optimierung nicht.

 

[Meniskusschaden]

Jetzt nur noch die Frage wieso sollte ich die obere Schranke n auf sqrt(n) setzen :-O kann mir das jemand mal genau erklären?

Wenn du einen Teiler hast, der größer als die Wurzel ist, muß es dazu ja auch einen passenden zweiten Teiler geben, der kleiner als die Wurzel ist und den hast du dann ja bereits gefunden und weißt somit, dass es keine Primzahl ist.

Denn wie schon gesagt gibt das für mich wenig sinn wenn ich 2-20 Primzahlen suche und er bei n=20 sqrt = 4 macht

Selbst wenn die Wurzel aus 20 tatsächlich vier wäre, müsstest du die vier natürlich dazu nehmen. Wenn der Teilerkandidat genau der Wurzel entspricht, gehört er gerade noch zum relevanten Bereich (Beispiel 25 und 5). Die Wurzel aus 20 ist aber größer als vier, also gehört vier sowieso dazu.