Übung: Primzahlen Berechnen

Mit dem Laden des Videos akzeptierst du die Datenschutzerklärung von YouTube. Wenn du die Menge an Daten reduzieren möchtest, die YouTube von dir sammelt, solltest du dich vorher aus deinem YouTube-Account ausloggen, das Speichern von Cookies für das Google-Ads-Programm deaktivieren und/oder Cookies im Browser blockieren.

YouTube immer automatisch laden

Inhaltsverzeichnis

Als Text lesen

Lass uns mal ein etwas größeres Beispiel besprechen: Ein Programm, das alle Primzahlen bis zu einer bestimmten Zahl berechnet.

Zur Erinnerung: Primzahlen sind alle positiven Ganzzahlen, die genau zwei unterschiedliche Teiler haben, nämlich 1 und sich selbst.

Beispiele:

7 ist eine Primzahl, weil sie nur durch die Zahlen 1 und 7 teilbar ist
10 ist keine Primzahl, weil 10 durch 1, 2, 5, und 10 teilbar ist
Die 1 selbst ist keine Primzahl, weil sie nur einen einzigen Teiler hat, nämlich 1

Um einen einfachen Algorithmus, also ein Rechenverfahren, zu entwickeln, der herausfindet, ob eine gegebene Zahl n eine Primzahl ist oder nicht, kann man folgendermaßen vorgehen:

Überprüfe, ob n kleiner ist als 2, falls ja ist n definitiv keine Primzahl
Iteriere durch alle Zahlen von 2 bis n - 1
Falls mindestens eine dieser Zahlen ein Teiler von n ist, ist n keine Primzahl
Ansonsten hat n keine Teiler zwischen 2 und n - 1 und muss daher eine Primzahl sein

a) Schreibe ein Programm, das überprüft, ob eine gegebene Zahl n eine Primzahl ist.

b) Modifiziere anschließend dein Programm so, dass es alle Primzahlen bis zu einer gewissen Zahl max (z.B. max = 100) ausgibt. (Hier reicht die Ausgabe der Zahl ohne weiteren Text.)

Die ersten Primzahlen lauten: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 71, 73, 79, 83, 97, ...

Mit dem Laden des Online Editors akzeptierst du die Datenschutzerklärung von JDoodle, einem Produkt der Nutpan pty Ltd (Australien). JDoodle verwendet die Tools reCAPTCHA und Google Analytics, wodurch Daten an Google übertragen werden können. Ich habe leider keinen Einfluss auf diesen Prozess. Du kannst Google Analytics über ein Browserplugin deaktivieren.

Online Editor immer automatisch laden

c) Gib alle Primzahlen von 1_000_000 bis 1_001_000 aus. Was fällt dir hinsichtlich der Ausführungsdauer auf? Wie könnte man das Problem beheben? Überlege dir hierzu, was genau in jeder Iteration passiert.

In Java lassen sich Zahlen übersichtlicher darstellen, indem man Tausender-Blöcke durch einen Unterstrich trennt:

10000 ist das gleiche wie 10_000.

Häufige Fehlerquellen

prime wurde kein initialer Wert gegeben: error: variable prime might not have been initialized
Fall für Zahlen kleiner 2 vergessen
Grenzen der for-Schleife falsch: Es muss von 2 bis n - 1 iteriert werden
prime genau falsch herum gesetzt: prime muss nur dann false sein, falls n < 2 oder es einen Teiler zwischen 2 und n - 1 gibt

Lösungsvorschlag Teilaufgabe a)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class Primes {
    public static void main(String[] args) {
        int n = 97;
        // Wir nehmen erstmal an, dass n eine Primzahl ist
        boolean prime = true;
        if (n < 2) {
            // Keine Zahl kleiner 2 ist eine Primzahl
            prime = false;
        } else {
            // Iteriere von 2 bis n - 1
            for (int i = 2; i < n; i++) {
                // Überprüfe, ob i ein Teiler von n ist
                if (n % i == 0) {
                    /*
                     * n hat mindestens einen Teiler im Intervall [2, n-1]
                     * und ist damit keine Primzahl
                     */
                    prime = false;
                }
            }
        }
        if (prime) {
            System.out.println(n + " ist eine Primzahl");
        } else {
            System.out.println(n + " ist keine Primzahl");
        }
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Lösungsvorschlag Teilaufgabe b)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Primes {
    public static void main(String[] args) {
        int max = 100;
        // Teste alle Zahlen von 2 bis max
        for (int n = 2; n <= max; n++) {
            boolean prime = true;
            /*
             * Überprüfung, ob n < 2 ist nicht notwendig,
             * weil wir erst bei n = 2 anfangen
             */
            for (int i = 2; i < n; i++) {
                if (n % i == 0) {
                    prime = false;
                }
            }
            if (prime) {
                System.out.println(n);
            }
        }
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Lösungsvorschlag Teilaufgabe c)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/*
 * Die Ausführungsdauer nimmt mit der Größe der Eingabe-Zahlen stark zu,
 * denn für jede Zahl n muss durch alle Zahlen von 2 bis n-1 iteriert werden.
 *
 * Möglichkeiten, die Laufzeit zu verbessern:
 *
 * 1) Sobald herausgefunden wurde, dass eine Zahl einen Teiler hat,
 *    müssen die restlichen Zahlen bis n-1 nicht mehr überprüft werden.
 *    Die Schleife kann also abgebrochen werden.
 *    Wie das geht, zeige ich dir auf der nächsten Seite.
 *
 * 2) Anstatt bis n-1 zu laufen, kann bereits bei der Quadratwurzel
 *    von n gestoppt werden*. Unsere Schleifen-Bedingung kann also
 *    verbessert werden zu: i * i <= n
 *
 *    *Falls dich der Grund interessiert, ist hier der Beweis:
 *    Jede (natürliche) Zahl, die keine Primzahl ist, ist zerlegbar in
 *    zwei Faktoren a und b, sodass a * b = n.
 *    Falls wir bereits überprüft haben,
 *    dass alle Zahlen bis zu √n keine Teiler von n sind,
 *    müssten beide dieser Faktoren größer sein als √n.
 *    Dann wäre aber n = a * b größer als √n * √n und damit n > n.
 *    Das ist ein Widerspruch, und somit muss n eine Primzahl sein.
 *
 *    Im folgenden siehst du eine verbesserte Implementierung
 *    mit Umsetzung dieser Idee. Überzeuge dich gerne selbst davon,
 *    dass dies um ein Vielfaches schneller ist, als der naive Ansatz:
 */
public class Primes {
    public static void main(String[] args) {
        int max = 1_001_000;
        for (int n = 1_000_000; n <= max; n++) {
            boolean prime = true;
            // Iteriere von 2 bis √n
            for (int i = 2; i * i <= n; i++) {
                if (n % i == 0) {
                    prime = false;
                }
            }
            if (prime) {
                System.out.println(n);
            }
        }
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Dir gefällt meine Arbeit?

Allgemein	Social	Rechtliches
Home	Instagram	Datenschutz
Über	YouTube	Impressum
	TikTok
	Ko-fi