Ich hatte noch ein bisschen überlegt, habe aber keine Lust meine Ideen auszuimplementieren.
Prinzipiell gehe ich davon aus, dass das forward-domain-restriction-Prinzip des Sieb des Erastosthenes (hoffentlich richtig geschrieben) schneller als das Prüfen anhand bereits berechneter Primzahlen ist.
Dafür benötigt das Sieb des Erastosthenes mehr Speicher (nicht getestet).
Für die Annahme, dass das Sieb des Erastosthenes mehr Speicher mehr Speicher als die Primzahlenliste benötigt spricht folgendes Programm:
[CODE lang="java" title="MaxPrimeGapFromFile"]package ???;
import java.io.IOException;
public class MaxPrimeGapFromFile
{
public static void main(final String[] args)
throws IOException
{
final PrimesFromCsvFileIterator primesFromCsvFileIterator = new PrimesFromCsvFileIterator();
int lastPrime = primesFromCsvFileIterator.getPrime();
int maxPrimeGap = 0;
final IntTreeBag histogramm = new IntTreeBag();
while ( primesFromCsvFileIterator.next() )
{
final int prime = primesFromCsvFileIterator.getPrime();
final int primeGap = prime - lastPrime;
if ( primeGap > maxPrimeGap)
{
System.out.println( primeGap + " " + prime );
}
histogramm.increment( primeGap );
maxPrimeGap =
Math.max(
maxPrimeGap ,
primeGap );
lastPrime = prime;
}
System.out.println( "max prime gap: " + maxPrimeGap );
System.out.println( "histogramm size: " + histogramm.size() );
System.out.println( histogramm );
}
}
[/CODE]
[CODE lang="java" title="IntTreeBag"]package ???;
import java.util.TreeMap;
@SuppressWarnings("serial")
public class IntTreeBag
extends TreeMap<Integer, Integer>
{
public void increment(
final int key )
{
final int oldValue;
final Integer oldValueObj = get( key );
if ( oldValueObj == null )
{
oldValue = 0;
}
else
{
oldValue = oldValueObj;
}
this.put( key , oldValue + 1 );
}
}
[/CODE]
[CODE title="MaxPrimeGapFromFile Konsolen-Ausgabe"]1 3
2 5
4 11
6 29
8 97
14 127
18 541
20 907
22 1151
34 1361
36 9587
44 15727
52 19661
72 31469
86 156007
96 360749
112 370373
114 492227
118 1349651
132 1357333
148 2010881
154 4652507
max prime gap: 154
histogramm size: 78
{1=1, 2=86027, 4=85832, 6=146518, 8=62750, 10=80399, 12=97826, 14=52826, 16=37688, 18=66465, 20=33777, 22=29583, 24=41731, 26=18928, 28=20591, 30=33960, 32=10100, 34=10536, 36=16301, 38=7196, 40=8600, 42=11657, 44=4492, 46=3822, 48=6305, 50=3449, 52=2412, 54=4054, 56=1862, 58=1753, 60=3194, 62=910, 64=980, 66=1664, 68=625, 70=906, 72=771, 74=392, 76=319, 78=612, 80=279, 82=197, 84=429, 86=122, 88=118, 90=276, 92=76, 94=73, 96=119, 98=52, 100=73, 102=63, 104=35, 106=27, 108=51, 110=26, 112=18, 114=34, 116=14, 118=8, 120=21, 122=6, 124=7, 126=17, 128=4, 130=2, 132=10, 134=3, 136=4, 138=6, 140=4, 142=2, 144=1, 146=1, 148=2, 150=1, 152=1, 154=3}
[/CODE]
Am Ende ist die Lücke 154 Bit gross, es würde aber ein 32-Bit-Integer zum Vermerken der Primzahl ausreichen.
Bei höheren Primzahlen werden sicher auch die Lücken grösser.
Nun hatte ich folgende Idee:
Um mehr Speicher zu haben (mehr Primzahlen berechnen zu können) könnte man den forward-Speicher als Sparse-Array aufbauen.
Wenn das Sparse-Array Ranges speichert, fallen irgendwann die Lücken zu einem Range zusammen, während einzelne im hohen Bereich liegende Streichungen als Werte gespeichert werden.
Das Sparse-Array könnte auch Bereiche negiert speichern, wenn dies Speicher spart.
Weitere Variante: Daten auf Disk auslagern.
Weitere Variante: Wenn man die vorherigen Primzahlen nicht vermerkt, benötigt man noch weniger Speicher, aber sicher mehr Zeit.
Es gibt noch das Sieb von Atkin, ist mir aber zu hoch, verstehe ich nicht:
de.wikipedia.org
Ist alles keine Frage und auch keine Aufforderung zur Diskussion, nur meine Gedanken, eventuell zum Wiederfinden durch mich selbst.