Wieso werden nicht alle Primzahlen bis 1000 in meine Liste gepackt ?

[sserio]

package ProjectEuler3;

import java.util.List;
import java.util.ArrayList;

public class Main {

public static void main(String[] args) {
findPrimeNumbers(1000);

}

public static void findPrimeNumbers(int number) {
List<Integer> list = new ArrayList<>();
int counter = 0;
if (number < 2) {
throw new IllegalArgumentException(" 1 and 2 aren't prime numbers");
}
for (int i = 2; i < number; i++) {
for (int j = 2; j < 10; j++) {
if (i % j == 0) {
counter++;
}
}
if (counter == 1) {
list.add(i);
counter = 0;
}
}
System.out.println(list);
}
}

Zurzeit sind bei mir nur die Zahlen 2 und 3 in der Liste.

 

[sserio]

Zurzeit sind bei mir nur die Zahlen 2 und 3 in der Liste.

nochmal eine Korrektur ich habe es jetzt hinbekommen, weiß aber nicht ob das so wirklich schnell und effektiv ist. Verbesserungsvorschläge nehme ich gerne an

import java.util.List;
import java.util.ArrayList;

public class Main {

public static void main(String[] args) {
findPrimeNumbers();

}

public static void findPrimeNumbers() {
List<Integer> list = new ArrayList<>();
int counter = 0;
int zaehler = 0;
for (int i = 2; i < 1000; i++) {
for (int j = 2; j < 1000; j++) {
if (isTrue(i, j)) {
counter++;
}
}
if (counter == 1) {
counter = 0;
list.add(i);
zaehler++;
} else counter = 0;
}
System.out.println(list);
System.out.println(zaehler);
}

public static boolean isTrue(int n, int m) {
return n % m == 0;
}
}

 

[Gelöschtes Mitglied 65838]

du kannst es anders angehen...

list;
list.add(2);
foreach ( number in 1000 )
    foreach( prime in list )
        if( number % prime == 0 )
            => keine Primzahl ist durch prime teilbar
           => kann man eig breaken
          
        if( war durch gar nichts teilbar von der Liste )
            => ist eine Neue Primzahl und list.add(number)

2 ist eine Primzahl übrigens 🙂

eine Zahl ist dann eine primzahl wenn sie nicht durch primzahlen geteilt werden kann.. du probierst zb 4 aus bei 16 das geht aber 4 ist keine primzahl dh der fall ist schon bei 2 abgedeckt => unnötig deswegen ist deines viel langsamer

 

[sserio]

du kannst es anders angehen...

list;
list.add(2);
foreach ( number in 1000 )
    foreach( prime in list )
        if( number % prime == 0 )
            => keine Primzahl ist durch prime teilbar
           => kann man eig breaken
         
        if( war durch gar nichts teilbar von der Liste )
            => ist eine Neue Primzahl und list.add(number)

2 ist eine Primzahl übrigens 🙂

eine Zahl ist dann eine primzahl wenn sie nicht durch primzahlen geteilt werden kann.. du probierst zb 4 aus bei 16 das geht aber 4 ist keine primzahl dh der fall ist schon bei 2 abgedeckt => unnötig deswegen ist deines viel langsamer

aber ich weiß ja noch garnicht ob meine zahlen primzahlen sind (Zeile 5), soll ich dann immer wieder durch die Liste gehen?

 

[Gelöschtes Mitglied 65838]

du hast immer die 2 drin

und jetzt machst du bis 10 die zahlen

3 => 3 % 2 = 1 => list.add(3)
4 => 4 % 2 = 0 => break;
// du musst alle elemente der liste durchlatschen
5 => 5 % 2 = 1 => 5 % 3 = 2 => list.add(5)
6 => 6 % 2 =>

 

[mihe7]

aber ich weiß ja noch garnicht ob meine zahlen primzahlen sind (Zeile 5), soll ich dann immer wieder durch die Liste gehen?

Wenn Du eine effiziente Implementierung suchst -> Sieb des Eratosthenes.

 

[Gelöschtes Mitglied 65838]

bei "ich hab es gerade geschafft 2 for schleifen zu verschachteln" sollte man vllt mit algorithmen etwas warten @mihe

 

[mihe7]

OK, dann lösen wir das ganze halt mal von vorne:

        for (int i = 2; i < number; i++) {
           for (int j = 2; j < 10; j++) {

Was soll der Käse mit der 10?

Oder hier

        for (int i = 2; i < 1000; i++) {
           for (int j = 2; j < 1000; j++) {

die 1000?

Bei solchen Dingen empfiehlt es sich, den Kopf einzuschalten:

Die äußere Schleife gibt die Zahl an, die dahingehend überprüft werden soll, ob es sich um eine Primzahl handelt. Wir wissen, dass 2 die kleinste Primzahl ist, also können wir bei 3 anfangen. Wir wissen auch, dass eine Primzahl ungerade ist, also brauchen wir nur ungerade Zahlen zu betrachten.

Die innere Schleife gibt einen möglichen Teiler dieser Zahl an. Die Frage ist, ob eine Zahl i durch eine Zahl j teilbar ist. Dann gäbe es eine Zahl k mit j*k=i. Außerdem muss der Teiler einer ungeraden Zahl selbst ungerade sein, denn nur das Produkt zweier ungerader Zahlen liefert wird eine ungerade Zahl.

Wie groß kann j denn maximal sein? Muss wirklich bis i geprüft werden?

Nein, weil die Multiplikation kommutativ ist. Hätte man z. B. i=1 geprüft, damit wäre automatisch auch i erledigt denn 1*i = i*1 = i. Die größtmögliche Teiler von i kann nicht größer als die Quadratwurzel von i sein, d. h. j <= sqrt(i) oder andersrum j*j <= i

Damit ergibt sich nun:

System.out.println("2 ist Primzahl");
for (int zahl = 3; zahl < 1000; zahl += 2) {
    boolean istPrimzahl = true;
    int maxTeiler = (int) Math.sqrt(zahl);
    for (int teiler = 3; istPrimzahl && teiler <= maxTeiler; teiler += 2) {
        if (zahl % teiler == 0) {
            istPrimzahl = false;
        }
    }
    if (istPrimzahl) {
        System.out.printf("%d ist Primzahl!%n", zahl);
    }
}

Der Algorithmus von @Joreyk geht noch einen Schritt weiter: statt immer alle ungeraden Teiler zu prüfen, prüft er nur die bereits gefundenen Primzahlen, was natürlich noch sehr viel effizienter ist:

System.out.println("2 ist Primzahl");
int[] primzahlen = new int[1000];
int anzahl = 0; // bereits gefundene Primzahlen (ohne die 2)
for (int zahl = 3; zahl < 1000; zahl += 2) {
    boolean istPrimzahl = true;
    for (int teilerIndex = 0; istPrimzahl && teilerIndex < anzahl; teilerIndex++) {
        if (zahl % primzahlen[teilerIndex] == 0) {
            istPrimzahl = false;
        }
    }
    if (istPrimzahl) {
        System.out.printf("%d ist Primzahl!%n", zahl);
        primzahlen[anzahl] = zahl;
        anzahl++;
    }
}
System.out.printf("%d Primzahlen gefunden\n", anzahl+1);

 

[sserio]

OK, dann lösen wir das ganze halt mal von vorne:

        for (int i = 2; i < number; i++) {
           for (int j = 2; j < 10; j++) {

Was soll der Käse mit der 10?

Oder hier

        for (int i = 2; i < 1000; i++) {
           for (int j = 2; j < 1000; j++) {

die 1000?

Bei solchen Dingen empfiehlt es sich, den Kopf einzuschalten:

Die äußere Schleife gibt die Zahl an, die dahingehend überprüft werden soll, ob es sich um eine Primzahl handelt. Wir wissen, dass 2 die kleinste Primzahl ist, also können wir bei 3 anfangen. Wir wissen auch, dass eine Primzahl ungerade ist, also brauchen wir nur ungerade Zahlen zu betrachten.

Die innere Schleife gibt einen möglichen Teiler dieser Zahl an. Die Frage ist, ob eine Zahl i durch eine Zahl j teilbar ist. Dann gäbe es eine Zahl k mit j*k=i. Außerdem muss der Teiler einer ungeraden Zahl selbst ungerade sein, denn nur das Produkt zweier ungerader Zahlen liefert wird eine ungerade Zahl.

Wie groß kann j denn maximal sein? Muss wirklich bis i geprüft werden?

Nein, weil die Multiplikation kommutativ ist. Hätte man z. B. i=1 geprüft, damit wäre automatisch auch i erledigt denn 1*i = i*1 = i. Die größtmögliche Teiler von i kann nicht größer als die Quadratwurzel von i sein, d. h. j <= sqrt(i) oder andersrum j*j <= i

Damit ergibt sich nun:

System.out.println("2 ist Primzahl");
for (int zahl = 3; zahl < 1000; zahl += 2) {
    boolean istPrimzahl = true;
    int maxTeiler = (int) Math.sqrt(zahl);
    for (int teiler = 3; istPrimzahl && teiler <= maxTeiler; teiler += 2) {
        if (zahl % teiler == 0) {
            istPrimzahl = false;
        }
    }
    if (istPrimzahl) {
        System.out.printf("%d ist Primzahl!%n", zahl);
    }
}

Der Algorithmus von @Joreyk geht noch einen Schritt weiter: statt immer alle ungeraden Teiler zu prüfen, prüft er nur die bereits gefundenen Primzahlen, was natürlich noch sehr viel effizienter ist:

System.out.println("2 ist Primzahl");
int[] primzahlen = new int[1000];
int anzahl = 0; // bereits gefundene Primzahlen (ohne die 2)
for (int zahl = 3; zahl < 1000; zahl += 2) {
    boolean istPrimzahl = true;
    for (int teilerIndex = 0; istPrimzahl && teilerIndex < anzahl; teilerIndex++) {
        if (zahl % primzahlen[teilerIndex] == 0) {
            istPrimzahl = false;
        }
    }
    if (istPrimzahl) {
        System.out.printf("%d ist Primzahl!%n", zahl);
        primzahlen[anzahl] = zahl;
        anzahl++;
    }
}
System.out.printf("%d Primzahlen gefunden\n", anzahl+1);

Danke für deine Antwort, habe es mittlerweile irgendwie selber geschafft, jedoch mit einem neuen Weg