Du verwendest einen veralteten Browser. Es ist möglich, dass diese oder andere Websites nicht korrekt angezeigt werden. Du solltest ein Upgrade durchführen oder ein alternativer Browser verwenden.
Wieso werden nicht alle Primzahlen bis 1000 in meine Liste gepackt ?
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);
}
}
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
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
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
for (int i = 2; i < number; i++) {
for (int j = 2; j < 10; j++) {
Was soll der Käse mit der 10?
Oder hier
Java:
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:
Java:
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:
Java:
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);
for (int i = 2; i < number; i++) {
for (int j = 2; j < 10; j++) {
Was soll der Käse mit der 10?
Oder hier
Java:
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:
Java:
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:
Java:
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);