Primzahlen - die ersten 100

[Java The Hutt]

Grüße euch 🙂

Ich versuche gerade ein Programm zu schreiben, welches mir die 1. 100 Primzahlen ausgibt.

Folgendes Programm:

public class Primzahlen {

    public static void main(String[] args) {

        double zahl = 0;
        int counter = 0;

        while (counter <= 25) {
            zahl++;


            for (int i = 2; i <= Math.sqrt(zahl); i++) {    //Teiler Maximal so groß wie Wurzel der Zahl
                if (zahl % i == 0) {
                    System.out.println(zahl);

            
                    

                    counter++;
                    break;    //Raus aus der For-Schleife, nachdem Teiler gefunden.
                
                
                }
                
            }
        }

        System.out.println("Durchgänge durch Schleife\t" + zahl);

    }
}

Jedoch habe ich zwei Probleme:
Das erste, er gibt mir die Zahlen aus, die keine Primzahlen sind. Und Primzahlen selber gibt er nicht aus. Wie kann ich das realisieren?
Das Zweite Problem:
Die ersten 100 Primzahlen gehen bis 541. Meine Schleife geht jedoch nur bis 134. Also Zählt er teilweise doppelt hoch.

Ich bitte um Hilfe 🙂

 

[mihe7]

Das erste, er gibt mir die Zahlen aus, die keine Primzahlen sind. Und Primzahlen selber gibt er nicht aus.

Naja, Du gibst ja eine Zahl aus, sobald diese ohne Rest durch i teilbar ist. Das passt jetzt nicht unbedingt so ganz zur Definition von Primzahlen, oder?

 

[Java The Hutt]

Naja, Du gibst ja eine Zahl aus, sobald diese ohne Rest durch i teilbar ist. Das passt jetzt nicht unbedingt so ganz zur Definition von Primzahlen, oder?

Ja, sinnvoll wäre if (zahl % i != 0),a der dann funktioniert die ganze Schleife nicht mehr. 🙁

 

[mihe7]

Nein, der Test auf die Teilbarkeit war schon sinnvoll, nur die Reaktion darauf ist falsch.

 

[Java The Hutt]

Nein, der Test auf die Teilbarkeit war schon sinnvoll, nur die Reaktion darauf ist falsch.

Ich weiß nicht weiter. Ich probiere das schon seit vielen Stunden zu lösen 😀
Hast du einen Tipp für mich?

 

[mihe7]

Du bist ja auch ganz nah an der Lösung. Zu welchem Zweck hast Du denn die innere Schleife?

 

[Java The Hutt]

Du bist ja auch ganz nah an der Lösung. Zu welchem Zweck hast Du denn die innere Schleife?

Die innere Schleife ist dafür da, um i, also den möglichen Teiler, hochzuzählen, bis maximal die Wurzel der Zahl und somit zu überprüfen, ob die Zahl teilbar ist,

 

[mihe7]

D. h. Du könntest vorab eine Variable auf false setzen und nach der Schleife sagt Dir die Variable, ob die Zahl teilbar ist...

 

[Java The Hutt]

So in etwa?

Spoiler: Code mit Boolean

public class Primzahlen {

    public static void main(String[] args) {

        double zahl = 0;
        int counter = 0;
        boolean istPrimzahl = false;

        while (counter <= 25) {
            zahl++;


            for (int i = 2; i <= Math.sqrt(zahl); i++) {    //Teiler Maximal so groß wie Wurzel der Zahl
                if (zahl % i == 0) {
                   
                    istPrimzahl = true;

           
                 

                    counter++;
                    break;    //Raus aus der For-Schleife, nachdem Teiler gefunden.
               
               
                } if (istPrimzahl) {
                    System.out.println(zahl);
               
                }
            }
           
           
           
        }

        System.out.println("Durchgänge durch Schleife\t" + zahl);

    }
}

 

[mihe7]

Jein.
1. Du hast vorhin geschrieben, dass Du in der Schleife prüfst, ob die Zahl teilbar ist, nicht ob sie eine Primzahl ist. Mach aus "istPrimzahl" ein "istTeilbar" (oder tausche true und false) dann stimmt das soweit.
2. Die Prüfung, ob die Variable true ist, muss außerhalb der Schleife passieren.

 

[Java The Hutt]

Spoiler: Programm, korrekt

public class Primzahlen {

    public static void main(String[] args) {

        double zahl = 0;
        int counter = 0;
        boolean istPrimzahl = false;                         // Es ist prinzipiell nie eine Primzahl

        while (counter < 100) {
            zahl++;

            for (int i = 2; i <= Math.sqrt(zahl); i++) {     // Teiler Maximal so groß wie Wurzel der Zahl
                if (zahl % i == 0) {

                    istPrimzahl = false;                     // Wenn Zahl Teilbar, dann keine Primzahl bestätigen

                    
                    break;                                     // Raus aus der For-Schleife, nachdem Teiler gefunden.

                } else {
                    istPrimzahl = true;                     // Sofern Zahl nie Teilbar, dann setze Primzahl = true

                }

            }
            if (istPrimzahl) {                                //Ausgabe der Zahl, wenn unteilbare Zahl erkannt
                System.out.println(zahl);
                counter++;                                    //Counter ++, sofern eine entdeckt wurde.
            }

        }

    }
}

Eine Frage noch, die 100. Primzahl ist 541. Wieso werden 2 Primzahlen mehr angegeben?

 

[Java The Hutt]

Spoiler: Programm, korrekt

public class Primzahlen {

    public static void main(String[] args) {

        double zahl = 0;
        int counter = 0;
        boolean istPrimzahl = false;                         // Es ist prinzipiell nie eine Primzahl

        while (counter < 100) {
            zahl++;

            for (int i = 2; i <= Math.sqrt(zahl); i++) {     // Teiler Maximal so groß wie Wurzel der Zahl
                if (zahl % i == 0) {

                    istPrimzahl = false;                     // Wenn Zahl Teilbar, dann keine Primzahl bestätigen

                  
                    break;                                     // Raus aus der For-Schleife, nachdem Teiler gefunden.

                } else {
                    istPrimzahl = true;                     // Sofern Zahl nie Teilbar, dann setze Primzahl = true

                }

            }
            if (istPrimzahl) {                                //Ausgabe der Zahl, wenn unteilbare Zahl erkannt
                System.out.println(zahl);
                counter++;                                    //Counter ++, sofern eine entdeckt wurde.
            }

        }

    }
}

Eine Frage noch, die 100. Primzahl ist 541. Wieso werden 2 Primzahlen mehr angegeben?

Erledigt, die 2 und 3 wird ja nicht mit ausgegeben 😀
Was kann ich machen, außer manuell die 2 und 3 ausgeben zu lassen? 😀

 

[mihe7]

Nein. Die Idee ist ganz einfach: eine Zahl ist so lange eine Primzahl, bis das Gegenteil bewiesen ist.

while (counter < 100) {
    zahl++;  

    // wir gehen davon aus, dass zahl eine Primzahl ist
    boolean istPrimzahl = true;

    // gilt die Primzahl-Eigenschaft für alle möglichen Teiler zwischen 2 und sqrt(x)?
    for (int i = 2; i <= Math.sqrt(zahl); i++) {
        if (zahl % i == 0) {
            istPrimzahl = false;
        }
    }

    // falls ja, ist zahl eine Primzahl
    if (istPrimzahl) {
        counter++;
    }
}

Der Code lässt sich noch stark optimieren, aber jetzt geht es erstmal ums Prinzip.

 

[Java The Hutt]

Spoiler: Zitat

Ich danke Dir für die Hilfe!

Nein. Die Idee ist ganz einfach: eine Zahl ist so lange eine Primzahl, bis das Gegenteil bewiesen ist.

while (counter < 100) {
    zahl++; 

    // wir gehen davon aus, dass zahl eine Primzahl ist
    boolean istPrimzahl = true;

    // gilt die Primzahl-Eigenschaft für alle möglichen Teiler zwischen 2 und sqrt(x)?
    for (int i = 2; i <= Math.sqrt(zahl); i++) {
        if (zahl % i == 0) {
            istPrimzahl = false;
        }
    }

    // falls ja, ist zahl eine Primzahl
    if (istPrimzahl) {
        counter++;
    }
}

Der Code lässt sich noch stark optimieren, aber jetzt geht es erstmal ums Prinzip.

Danke für Deine Unterstützung! Jetzt Interessiert mich aber, wie man den Code optimieren kann 🙂

 

[mihe7]

Naja:
1. muss man immer bis Math.sqrt(zahl) laufen?
2. muss man in jedem Schleifendurchlauf Math.sqrt(zahl) berechnen?
3. wie viele gerade Primzahlen kennst Du?

Wenn man 1. abgearbeitet hat, kann man den Schleifenrumpf noch umschreiben zu

istPrimzahl = (zahl % i != 0);

 

[Java The Hutt]

Naja:
1. muss man immer bis Math.sqrt(zahl) laufen?
2. muss man in jedem Schleifendurchlauf Math.sqrt(zahl) berechnen?
3. wie viele gerade Primzahlen kennst Du?

Wenn man 1. abgearbeitet hat, kann man den Schleifenrumpf noch umschreiben zu

istPrimzahl = (zahl % i != 0);

Okay verstehe.
1) Das Problem kann gelöst werden, nachdem ein Teiler gefunden wurde, ein "Break" genutzt wird, um die Schleife zu beenden.
2) Dafür habe ich keine Idee 😀
Die Lösung für das 3. Problem ist doch, dass ich anstatt zahl++; zahl+=2 nehme, somit fallen die geraden zahlen raus.

 

[fhoffmann]

2) Dafür habe ich keine Idee

Du kannst die Wurzel vor der for-Schleife berechnen und dir in einer Variablen merken.

 

[mihe7]

Der Reihe nach:
1) Ja, Du kannst auch einfach istPrimzahl zur zusätzlichen Schleifenbedingung machen:

for (int i = 2; istPrimzahl && i <= Math.sqrt(zahl); i++)

2) Aktuell wird bei jedem Schleifendurchlauf Math.sqrt(zahl) berechnet. Das Ergebnis ändert sich aber nicht, daher kannst Du das vorab berechnen, entweder

int max = (int) Math.sqrt(zahl);
for (int i = 2; istPrimzahl && i<= max; i++)

oder kurz:

for (int i = 2, max = (int)Math.sqrt(zahl); i <= max; i++)

3) Ja, Du musst aber natürlich in der Schleife bei 3 beginnen und gerade Zahlen vorab berücksichtigen 🙂

// wir wissen, dass 2 die erste Primzahl ist, also:
int zahl = 2;
int counter = 1;

while (counter < 100) {
    zahl++;
    if (zahl % 2 != 0) { // nur ungerade Zahlen müssen berücksichtigt werden
        boolean istPrimzahl = true;    
        while (int i = 3, max = (int)Math.sqrt(zahl); istPrimzahl && i <= max; i+=2) {
             istPrimzahl = (zahl % i != 0); 
        }
        if (istPrimzahl) counter++;
    }
}
...