Primzahlen sind ein interessantes Thema. Mich interessiert vorallem, wie ich schnellstmöglich Primzahlen berechnen kann. Deswegen rufe ich hier mal einen kleinen Contest aus. Wer programmiert die schnellste Funktion um
primär: alle Primzahlen bis zu einem vorgegebenen Wert in einer Liste/Array zu speichern?
sekundär (1): zu überprüfen ob eine Zahl eine Primzahl ist oder nicht?
sekundär (2): die nächste Primzahl die auf eine Zahl folgt zu ermitteln?
Programmiersprache ist erstmal egal. Natürlich hab ich auch schon etwas (in Java) programmiert, könnte mir aber vorstellen, dass da durchaus noch etwas an performance zu holen ist.
Alle Primzahlen von 0 - n speichern:
long time = System.currentTimeMillis();
int[] ar = new int[max / 4];
ar[0] = 2;
ar[1] = 3;
ar[2] = 5;
int temp = 0;
int pos = 3;
boolean prim = true;
for (int i = 7; i < max; i += 2) {
prim = true;
if (i % 3 != 0 && i % 5 != 0) {
temp = (int)Math.sqrt(i) + 1;
for (int j = 3; j < pos && ar[j] < temp; j++) {
if (i % ar[j] == 0) {
prim = false;
break;
}
}
if (prim) {
ar[pos++] = i;
if (pos == ar.length) {
System.arraycopy(ar, 0, (ar = new int[ar.length + 5000]), 0, ar.length - 5001);
}
}
}
}
System.out.println(System.currentTimeMillis() - time + "/" + pos);
System.out.println(ar[pos - 1]);
return ar;
}```
Testergebnisse mit einem Zugesicherten Speicher von 1024MB (DDR 400 wenn mich nicht alles täuscht) in der Virtual Machine und einem Pentium IV mit 3,8 GHz und HT Technologie (Anwendung ist Single-Threaded):
**Alle Primzahlen bis 1.000.000:**
Benötigte Millisekunden: 187
Gefundene Primzahlen: 78498
Letzte Primzahl: 999983
**Alle Primzahlen bis 5.000.000:**
Benötigte Millisekunden: 1.500
Gefundene Primzahlen: 348.513
Letzte Primzahl: 4.999.999
**Alle Primzahlen bis 10.000.000:**
Benötigte Millisekunden: 3.719
Gefundene Primzahlen: 664.579
Letzte Primzahl: 9.999.991
**Alle Primzahlen bis 50.000.000:**
Benötigte Millisekunden: 31.890
Gefundene Primzahlen: 3.001.134
Letzte Primzahl: 49.999.991
**Alle Primzahlen bis 100.000.000:**
Benötigte Millisekunden: 82.034
Gefundene Primzahlen: 5.761.455
Letzte Primzahl: 99.999.989
**Alle Primzahlen bis 500.000.000:**
Benötigte Millisekunden: 756.711
Gefundene Primzahlen: 26.355.867
Letzte Primzahl: 499.999.993
Überprüfen ob Zahl eine Primzahl ist:
```public static boolean isPrim(int numb) {
if (numb == 2 || numb == 3) {
return true;
}
if (numb % 2 != 0 && numb % 3 != 0) {
int temp = (int)Math.sqrt(numb) + 1;
for (int j = 4; j < temp; j++) {
if (numb % j == 0) {
return false;
}
}
}
else {
return false;
}
return true;
}```
Nächste Primzahl auslesen:
```public static int getNextPrim(int numb) {
if (numb % 2 == 0) {
numb++;
}
while (true) {
if (isPrim(numb)) {
return numb;
}
numb += 2;
}
}```
).