Algorithmus gesucht: nächstgrößere Zahl, die bestimmter Regel entspricht

volkard

CStoll schrieb:

j=4*(i/4)+3;
if(j<i) j+=4;//warning C4711: condition is always false, isn't it?
for(;!isPrim(j);j+=4);

CStoll

@volkard: Sorry, dann sollte das wohl eher <= sein

volkard

SeppJ schrieb:

Darf ich vorschlagen ~~zu schummeln~~ die Aufgabenstellung kreativ zu interpretieren?
Du suchst dir eine möglichst große Primzahl mit der genannten Bedingung.

Cool!
Mersenne-Primzahlen haben die Form 2ⁿ−1 also 42^n-2-1 also 4(2^n-2-1)+3.
Und da gibt es große im Netz. Ich verzichte darauf, alle 12978189 Stellen der größten derzeit bekannten zu posten.

@SeppJ:
Sorry, gesucht ist die KLEINSTE Primzahl j >= i, für welche die Regel gilt. j - i ist nämlich Zusatzspeicher, den ich verbrate, nur mit dem Sinn, dass j obiger Regel entspricht. Von daher ...

volkard

algomat schrieb:

Hash-Datenstruktur, die ich schreiben will.

Und wie sind die Vollstandsbedingungen? Soll sie dynamisch wachsen?
Mal feste Zahlen genommen, mit 11 angefangen und immer die nächsthöhere ist ca 50% mehr.
Solche vorberechneten Arrays werden gerne benutzt.

int main(){
    using namespace std;
    cout<<"possibleHashSizes[]={";
    for(int j=11;j>0;j=findNextFunnyPrime(j+j/2))
        cout<<j<<',';
    cout<<"};\n";
}

Ausgabe:

int possibleHashSizes[]={11,19,31,47,71,107,163,251,379,571,859,1291,1951,
2927,4391,6599,9907,14867,22303,33479,50227,75347,113023,169567,254383,
381607,572419,858631,1287947,1931927,2897959,4347011,6520519,9780787,
14671183,22006843,33010343,49515547,74273327,111410003,167115019,250672547,
376008823,564013283,846019963,1269029947,1903544939,};

Das ist natürlich auch eine Idee, volkard. Tatsächlich ist der Speicher der Datenstruktur von Beginn an begrenzt, was in diesem Fall auch vollkommen ausreichend ist. In diesem Fall wäre es wohl echt effizienter, ein Array mit möglichen Werten zu halten.

Danke nochmal.

volkard

algomat schrieb:

Das ist natürlich auch eine Idee, volkard. Tatsächlich ist der Speicher der Datenstruktur von Beginn an begrenzt, was in diesem Fall auch vollkommen ausreichend ist. In diesem Fall wäre es wohl echt effizienter, ein Array mit möglichen Werten zu halten.

Danke nochmal.

Nicht nur das. Wenn wie bei meinem Beispiel der Füllstand zwischen 66% und 100% liegen darf, ist das ja ein exponentielles Wachstum der Zhalen im Array. Für 64 Bit wird das Array nur doppelt so lang wie für 32 Bit. Es bleibt lächerlich klein.

Oder zwischen 50% und 75% oder zwischen 53% und 80%, um die magische 80 zu benutzen.

csofti

Gibt es für die Aufgabe keine fertige Bibliothek?

int possibleHashSizes[]={11,19,31,47,71,107,163,251,379,571,859,1291,1951,
2927,4391,6599,9907,14867,22303,33479,50227,75347,113023,169567,254383,
381607,572419,858631,1287947,1931927,2897959,4347011,6520519,9780787,
14671183,22006843,33010343,49515547,74273327,111410003,167115019,250672547,
376008823,564013283,846019963,1269029947,1903544939,};

Wie wäre es alle Primzahlen in dem endlichen Bereich von Integer vorzuberechnen die diese Bedingung erfüllen und dann einfach mit binärer Suche die kleinste die größer ist als deine Zahl i, in dieser Tabelle zu suchen?
(Es scheinen doch relativ ewenige zu sein die gespeichert werden müssten)

volkard

MisterX schrieb:

Wie wäre es alle Primzahlen in dem endlichen Bereich von Integer vorzuberechnen die diese Bedingung erfüllen und dann einfach mit binärer Suche die kleinste die größer ist als deine Zahl i, in dieser Tabelle zu suchen?
(Es scheinen doch relativ ewenige zu sein die gespeichert werden müssten)

Hoffnungslos.
Es gibt unter n circa n/ln(n) Primzahlen, vermutlich n/ln(n)/2 Primzahlen mit dieser Bedingung.
Bis 1000000 also schon mehr als 36000. Bis 4Mrd für 32 Bit mag ich es gar nicht ausrechnen. Und ich strebe 64 Bit an.