ich habe da ein Problem,mir ein mehrdimensionales Array vorzustellen, denke ich. :autsch:
Schritt 1 meiner Aufgabe war es, ein Array boolean[] zu erstellen und darin 10000 booleans zu speichern. Danach sollte getestet werden, ob der Index eine Primzahl ist und je nachdem ob es so ist oder nicht, der Wert als boolean auf der Konsole ausgegeben werden. Ich habe mir also eine Methode geschrieben, die auf Primzahlen testen kann und ein boolean zurueckliefert:
public static boolean isPrimzahl(long zahl){
long prim = zahl;
if (prim <= 2) {
return (prim == 2);
}
for (long i = 2; i * i <= prim; i++) {
if (prim % i == 0) {
return false;
}
}
return true;
}
Diese Methode steht in meiner Klasse MyMath.
Als naechstes habe ich eine neue Klasse PrimZahlTest erstellt und diese hat wunderbar funktioniert.
private static boolean[] array;
public static void main(String[] args) {
boolean[] temp = PrimZahlTest.stufe1();
for (int i=0; i<10000;i++){
System.out.println(temp**);
}
}
public static boolean[] stufe1(){
array = new boolean[10000];
for (int i=0;i<array.length;i++) {
array** = MyMath.isPrimzahl(i);
}
return array;
}
Soweit, so gut. :toll:
Aber nun sollte Schritt 2 folgen.
Meine Herangehensweise sollte aehnlich sein.
private static boolean[][] array2;
public static void main(String[] args) {
boolean[][] temp = PrimZahlTest.stufe2();
for (int i=0;i<=10000;i++) {
System.out.println(temp**);
}
public static boolean[][] stufe2(){
array2 = new boolean[100][100];
for (int i=0;i<=100;i++) {
for (int j=0;j<=100;j++) {
array2**[j] = MyMath.isPrimzahl(i*j);
}
}
return array2;
}
Doch das hat nicht funktioniert. Ich weiss nicht so recht,wie ich mir dieses 100x100 vorstellen soll auf der Konsole und wie ich da ein boolean ausgeben soll, wenn ich an der Stelle [2][4] zum Beispiel bin, wie soll ich herausfinden, ob dieses Feld eine Primzahl als Index hat oder nicht?
Dabei Füllt man das Array als erstes komplett mit true für jedes Feld.
Die erste Primzahl die Sinn macht ist die Zwei.
array[2] == true
Jetzt geht man hin und setzt in diesem Array alle vielfachen von 2 auf false, da diese keine Primzahlen sein können bis man am Ende des Arrays angelangt ist.
Jetzt erhöht man den index um eins und kommt auf das feld array[3] == true, dieses ist wiederum True und drei somit eine Primzahl. Nun setzt man in diesem Array alle vielfachen von 3 auf false.
Jetzt erhöht man den Index um eins und kommt auf das feld array[4] == false, keine Primzahl. Man braucht nichts mehr tun, da alle vielfachen von 4 bereits auf false gesetzt wurden.
Man erhöht den Index um eins und kommt auf array[5] == true, also wieder alle vielfachen auf false setzen.
Dies macht man solange bis man ans Ende des Arrays gekommen ist.
Nun haben alle Primzahlen, den Wert true, alle anderen false.
Zu 2:
[4][2] kann man auch als 4 * 100 + 2 lesen. Also 402.
und um einen Boolean auf der Konsole darzustellen benotigt man eigentlich nur 2 Zeichen, bei denen man vereinbart, dass eines für “true” und das andere für “false” steht. 0 und 1sind bewährt, - und # sind aber deutlicher zu unterscheiden…
achja: die Kommandozeile ist standardmässig nur 80Zeichen breit, dass muss man vorher anpassen.
* @author CB
*/
public class SdE {
private static void sde(boolean[] sieb) {
int n = sieb.length;
a: for (int i = 3; i < n; i += 2) {
int sqrt = ((int) Math.sqrt(i)) + 1;
for (int j = 3; j < sqrt; j += 2) {
if (sieb[j] && i % j == 0) {
continue a; // keine Primzahl -> fortfahren
}
}
sieb** = true; // Primzahl
}
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
boolean[] sieb = new boolean[1000]; // Test von 0 bis 999
sde(sieb); // Aufruf von SdE mit false-Array sieb
sieb[2] = true;
for (int i = 0; i < sieb.length; i++) { // gib Zahl aus...
if (sieb**) { // ...wenn Bedingung zutrifft
System.out.println(i);
for (int j = 2; j < i; j++) { // ...prüfe sicherheitshalber noch mal
if (i % j == 0) {
System.out.println(false);
break; // doch eine Primzahl -> springen
}
}
}
}
}
}```
Jetzt wird nur durch bereits vorhandene Primzahlen geteilt. Eigentlich denkt man da ja an eine verkettete Liste, aber die erzeugt zu viel Overhead. (boolean ist auch nicht einfach nur ein Bit oder ein Byte)
Jetzt kannst du es ja so ändern, dass die Vielfachen der Primzahlen gestrichen werden.
Aber trotzdem kann man die Breite einstellen:
Im Konsolenfenster oben links auf das schwarze Icon klicken → Eigenschaften → Reiter „Layout“ → Unter Fensterpuffergröße die Breite auf einen anderen Wert, beispielsweise 150 festlegen.
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package sde;
/**
* @author CB
*/
public class SdE {
private static void sde1(boolean[] sieb) {
int n = sieb.length;
a: for (int i = 3; i < n; i += 2) {
int sqrt = ((int) Math.sqrt(i)) + 1;
for (int j = 3; j < sqrt; j += 2) {
if (sieb[j] && i % j == 0) {
continue a;
}
}
sieb** = true;
}
}
private static void sde2(boolean[] sieb) {
int n = sieb.length;
a: for (int i = 3; i < n; i += 2) {
if (sieb**) {
int j = i + i;
while (j < n) {
sieb[j] = false;
j += i;
}
}
}
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
long t1 = System.currentTimeMillis();
boolean[] sieb1 = new boolean[9999999];
sieb1[2] = true;
sde1(sieb1);
long t2 = System.currentTimeMillis();
boolean[] sieb2 = new boolean[9999999];
sieb2[2] = true;
for (int i = 3; i < sieb2.length; i += 2) {
sieb2** = true;
}
sde2(sieb2);
long t3 = System.currentTimeMillis();
for (int i = 0; i < sieb1.length; i++) {
if (sieb1** ^ sieb2**) {
System.out.println("i = " + i);
System.out.println("sieb1** = " + sieb1**);
System.out.println("sieb2** = " + sieb2**);
break;
}
}
System.out.println("(t2 - t1) = " + (t2 - t1));
System.out.println("(t3 - t2) = " + (t3 - t2));
}
}```
sde2 ist das "offizielle" "Sieb d. E."
sde1 ist ~ 28-mal langsamer als sde2 (sde2 ist also 28-mal so schnell; in Prozent: I don't know). Ich vermute, am meisten Power verbrät `int sqrt = ((int) Math.sqrt(i)) + 1;` und `i % j == 0)`.
Bitte sagt mir jetzt nicht, das sei Premature Optimization oder ein inkorrekter Benchmark.
Edit: Ich implementiere/schreibe das gerne auch noch mal mit einer Primzahlliste oder ich erkläre auch jede einzelne Zeile, falls gewünscht.
Eine Schleifeninvariante müsst ihr aber bringen.
Nö, natürlich nicht. Lass dir doch einfach mal die ersten Zehn Primzahlen ausgeben!
Mit beiden Algorithmen!
sde1 kann schonmal überhaupt nicht stimmen, da wird niemals etwas auf false gesetzt. Wie sollen da nicht-Primzahlen gefunden werden?
Aber mit sde2 sieht es genauso schlecht aus! Hätte man die ersten Zehn Primzahlen ausgegeben, dann hätte man wohl gemerkt, dass etwas nicht Stimmen kann wenn 4 und 8 als Primzahlen erkannt werden.
Beim Sieb des Eratosthenes fängt man bei 2 an und geht dann in einser-Schritten voran.
int sqrt = ((int) Math.sqrt(n)) + 1;
a: for (int i = 3; i < sqrt; i += 2) {```
@Landei , mit dem ich momentan nicht befreundet bin, hatte mir mal erklärt, warum das so ist.
@Majora : Bitte nicht von der Seite angreifen. Die Ausgabe beider Methoden/Prozeduren ist korrekt. Ein Array fängt bei Index 0 an. true bedeutet Primzahl, false bedeutet keine Primzahl. Gerne auch noch mal zum Testen:
Vollständiger Quelltext
[spoiler]```/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package sde;
/**
* @author CB
*/
public class SdE {
private static void sde1(boolean[] sieb) {
int n = sieb.length;
a:
for (int i = 3; i < n; i += 2) {
int sqrt = ((int) Math.sqrt(i)) + 1;
for (int j = 3; j < sqrt; j += 2) {
if (sieb[j] && i % j == 0) {
continue a;
}
}
sieb** = true;
}
}
private static void sde2(boolean[] sieb) {
int n = sieb.length;
int sqrt = ((int) Math.sqrt(n)) + 1;
a:
for (int i = 3; i < sqrt; i += 2) {
if (sieb**) {
int j = i + i;
while (j < n) {
sieb[j] = false;
j += i;
}
}
}
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
long t1 = System.currentTimeMillis();
boolean[] sieb1 = new boolean[102];
sieb1[2] = true;
sde1(sieb1);
long t2 = System.currentTimeMillis();
boolean[] sieb2 = new boolean[102];
sieb2[2] = true;
for (int i = 3; i < sieb2.length; i += 2) {
sieb2** = true;
}
sde2(sieb2);
long t3 = System.currentTimeMillis();
for (int i = 0; i < sieb1.length; i++) {
if (sieb1** || sieb2**)
System.out.println(i);
if (sieb1** ^ sieb2**) {
System.out.println("i = " + i);
System.out.println("sieb1** = " + sieb1**);
System.out.println("sieb2** = " + sieb2**);
break;
}
}
System.out.println("(t2 - t1) = " + (t2 - t1));
System.out.println("(t3 - t2) = " + (t3 - t2));
}
}```[/spoiler]
Sry, ich weiß jetzt, was du meinst, der Fehler lag hier:
Vollständiger Quelltext zu S. d. E. 2
[spoiler]```/*
To change this template, choose Tools | Templates
and open the template in the editor.
*/
package sde;
/**
@author CB
*/
public class SdE { // true==Primzahl, false==Nicht-Primzahl
private static boolean[] sde1(int n) {
boolean[] sieb = new boolean[n];
sieb[2] = true;
a:
for (int i = 3; i < n; i += 2) {
int sqrt = ((int) Math.sqrt(i)) + 1;
for (int j = 3; j < sqrt; j += 2) {
if (sieb[j] && i % j == 0) {
continue a;
}
}
sieb** = true;
}
return sieb;
}
private static boolean[] sde2(int n) {
boolean[] sieb = new boolean[n];
sieb[2] = true;
for (int i = 3; i < n; i += 2) {
sieb** = true;
}
int sqrt = ((int) Math.sqrt(n)) + 1;
a: // überflüssig
for (int i = 3; i < sqrt; i += 2) {
if (sieb**) {
int j = i + i;
while (j < n) {
sieb[j] = false;
j += i;
}
}
}
return sieb;
}
/**
@param args the command line arguments
*/
public static void main(String[] args) {
long t1 = System.currentTimeMillis();
boolean[] sieb1 = sde1(102);
long t2 = System.currentTimeMillis();
boolean[] sieb2 = sde2(102);
long t3 = System.currentTimeMillis();
for (int i = 0; i < sieb1.length; i++) { // Kontrolle
if (sieb1** || sieb2**) {
System.out.println(i);
}
if (sieb1** ^ sieb2**) {
System.out.println("i = " + i);
System.out.println("sieb1** = " + sieb1**);
System.out.println("sieb2** = " + sieb2**);
break;
}
}
Auf eine eigene Kontrollmethode würde ich mich hier nicht verlassen, insbesondere da sich BigInteger.isProbablePrime dafür direkt anbietet (und nein, solange man im Long-Bereich unterwegs ist, ist da nicht “probable”).
@Landei , ist folgende Methode denn korrekt -oder lässt sich noch etwas beschleunigen?
boolean[] sieb = new boolean[n];
sieb[2] = true;
for (int i = 3; i < n; i += 2) {
sieb** = true;
}
final int sqrt = ((int) Math.sqrt(n)) + 1;
for (int i = 3; i < sqrt; i += 2) {
if (sieb**) {
int j = i + i;
while (j < n) {
sieb[j] = false;
j += i;
}
}
}
return sieb;
}```
Darauf aufbauend könnte man ja eine Klasse mit Attribut sieb schreiben, welche für int/long durch Teilen/Moduloen durch Primzahlen testet, ob das Argument eine Primzahl ist.
hmm … also entweder ist meine CPU schrott … oder die implementierung … aber BigInteger.isProablePrime() liefert bei mir sogar im INT bereich falsche ergebnisse : so sollen laut meiner ausgabe angeblich zahlen prime sein die sich durch 5 teilen lassen … oder auch solche die durch 3 teilbar sind … und da so diese methode im LONG-bereich richtige ergebnisse liefern ?
[QUOTE=Unregistered]hmm … also entweder ist meine CPU schrott … oder die implementierung … aber BigInteger.isProablePrime() liefert bei mir sogar im INT bereich falsche ergebnisse : so sollen laut meiner ausgabe angeblich zahlen prime sein die sich durch 5 teilen lassen … oder auch solche die durch 3 teilbar sind … und da so diese methode im LONG-bereich richtige ergebnisse liefern ?
ich muss meine hardware wohl reklamieren …[/QUOTE]
Muss an der Implementierung liegen. Da steckt normalerweise ein Miller-Rabin-Test dahinter, und für diesen sind (für einen bestimmten Bereich) „sichere“ Basen-Kombinationen bekannt (siehe Miller–Rabin primality test - Wikipedia ). Hast du mal ein paar Beispiele, wo es nicht funktioniert?
*** Edit ***
Eine ganz einfache Maßnahme wäre, für jede Primzahl p erst ab p² zu streichen, und dann mit Schrittweite 2p bis sqrt(n) . Es gibt zwar kleinere Zahlen, die durch p teilbar sind, die werden aber schoch durch Primzahlen kleiner als p „erledigt“.
Beispiel 7: 2|14, 3|21, 2|28, 5|35, 2|42, also ist 7² = 49 die erste Zahl, wo wir wirklich die Teilbarkeit durch 7 testen müssen.
So, wer ein bisschen Rechenpower hat, kann dieses durchlaufen lassen:
Versteckter Text
[spoiler]```/*
To change this template, choose Tools | Templates
and open the template in the editor.
*/
package sde;
/**
@author CB
*/
public class SdE {
public static boolean isPrime(int x) {
if (x <= 1) {
return false;
}
if (x == 2) {
return true;
}
for (int i = 2; i < x; i++) {
if (x % i == 0) {
return false;
}
}
return true;
}
private int[] sieb = new int[0];
public SdE() {
boolean[] sieb = sde((int) Math.ceil(Math.sqrt(Integer.MAX_VALUE)) + 1);
int j = 0;
for (boolean b : sieb) {
if (b) {
j++;
}
}
this.sieb = new int[j];
j = 0;
for (int i = 0; i < sieb.length; i++) {
if (sieb**) {
this.sieb[j++] = i;
}
}
}
private boolean[] sde(final int n) {
boolean[] sieb = new boolean[n];
sieb[2] = true;
for (int i = 3; i < n; i += 2) {
sieb** = true;
}
final int sqrt = (int) Math.sqrt(n) + 1;
for (int i = 3; i < sqrt; i += 2) {
if (sieb**) {
int j = i + i;
while (j < n) {
sieb[j] = false;
j += i;
}
}
}
return sieb;
}
public boolean istPrimzahl(final int x) {
if (x <= 1) {
return false;
}
final int sqrt = (int) Math.sqrt(x);
for (int i : sieb) {
if (i > sqrt) {
break;
}
if (x % i == 0) {
return false;
}
}
return true;
}
/**
@param args the command line arguments
*/
public static void main(String[] args) {
SdE sde = new SdE();
int x = -2;
while (x <= 101) {
boolean b1 = isPrime(x);
boolean b2 = sde.istPrimzahl(x);
if (b1 || b2) {
System.out.println("x = " + x);
}
if (b1 ^ b2) {
System.out.println("b1 = " + b1);
System.out.println("b2 = " + b2);
return;
}
x++;
}
System.out.println();
x = 999977;
while (x <= 1000101) {
boolean b1 = isPrime(x);
boolean b2 = sde.istPrimzahl(x);
if (b1 || b2) {
System.out.println("x = " + x);
}
if (b1 ^ b2) {
System.out.println("b1 = " + b1);
System.out.println("b2 = " + b2);
return;
}
x++;
}
System.out.println();
x = Integer.MAX_VALUE - 151;
while (x > 0) {
boolean b1 = isPrime(x);
boolean b2 = sde.istPrimzahl(x);
if (b1 || b2) {
System.out.println("x = " + x);
}
if (b1 ^ b2) {
System.out.println("b1 = " + b1);
System.out.println("b2 = " + b2);
return;
}
x++;
}
}
}```[/spoiler]
public static isPrime == Kontrollmethode, braucht lange, wie man sieht
private sde == Gibt ein Sieb mit Primzahlen auf true zurück
public istPrimzahl == Prüft durch Moduloen mit Primzahlen auf Primzahl
(int) Math.ceil(Math.sqrt(Integer.MAX_VALUE)) + 1 == Größe des Siebs, also bis Index n - 1
(int) Math.sqrt(n) + 1 == Bis exklusiv dieses Werts alle Vielfachen von Primzahlen streichen
(int) Math.sqrt(x) == Mit Primzahlen bis inklusiv dieses Werts moduloen
Bei mir stimmt die Ausgabe, bei euch auch?
Hoffentlich, hoffentlich, hoffentlich habe ich bei den Indexen, den Primzahlen oder den Arraylängen nicht irgendwo + 1 oder - 1 vergessen, also was falsch gemacht
Mal ein Algorithmus, der auf einem zweidimensionalen Array arbeitet und ein wie ich meine etwas anderen Ansatz hat.
Jede Zahl läßt sich eindeutig in seine Primfaktoren zerlegen.
Folglich läßt sich auch jede Zahl aus einem Produkt von Primzahlen generieren.
Genau dies macht sich dieser Algorithmus zu nutze.
Aus den Anfangs gegebenen Zahlen, 1 und 2. Werden die Produkte 2, 4, 8, 16, 32, etc. gebildet bis die Grenze erreicht ist.
Im nächtsten Schritt wird die 2 incrementiert zu 3. Da sich die drei noch nicht in der Liste der Produkte befindet, wird sie dort hinzugefügt sowie als Primzahl vermerkt.
Die Liste sieht nun wie folgt aus
2,3,4,8,16,32, etc.
Nun wird jedes Element dieser Liste mit Drei durchmultipliziert, bis man wiederum die Grenze erreicht.
Die Liste sieht nun wie folgt aus
2,3,4,6,8,12,16,18,24,32,36, etc.
Also alles Zahlen die ein Produkt aus den Primzahlen 2 und 3 sind.
4 ist in der Liste und braucht nicht weiter behandelt zu werden.
5 ist nicht drin.
Nun geht man die Liste mit 5, sowie den Potenzen von 5 durch.
public static boolean[] primes(int until){
boolean[][] x = new boolean[2][until];
x[1][1] = true;
for(int i = 2; i<until; i++){
if(!x[1]**){
x[0]**=true;
int border = (until-1)/i;
for(int j = 0; j<=border; j++){
if(x[1][j]){
x[1][j*i]= true;
}
}
}
}
return x[0];
}
public static void print(boolean[] primes){
for(int i = 0; i<primes.length; i++){
if(primes**){
System.out.println(i);
}
}
}
public static void main(String[] args) {
print(primes(100));
long t1 = System.currentTimeMillis();
primes(Integer.MAX_VALUE/10);
long t2 = System.currentTimeMillis();
System.out.println("(t2 - t1) = " + (t2 - t1));
}
}```
