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

Hallo,

Eingabe ist eine beliebige, natürliche Zahl i.
Ausgabe soll eine PRIMZAHL j >= i sein, für die gilt:
j = 4 * k + 3, für ein beliebiges k.

Das banalste was mir einfällt:

algorithmus getPrime(i):
    fuer alle j >= i:
        j := j - 3
        j := j / 4
        falls istPrimzahl(j) wahr ist:
            gib j zurueck

algorithmus istPrimzahl(j):
    wenn kein Teiler von 3 bis j - 1 zu finden:
        gib 'Wahr' zurück
    ansonsten:
        gib 'Falsch' zurück

Michael E.

Algorithmen für Primzahlen hatten wir schon viele in diesem Forum. Als letztes hatte camper eine umfangreichere Lösung.

Wenn der verwendete Primzahlalgorithmus jede Zahl einzeln testet (wie du es zum Beispiel machst), übergib ihm jede vierte Zahl, die größer als i is (sodass j % 4 == 3). Wenn der Primzahlalgorithmus sowieso auf Intervallen arbeitet, kommt die Prüfung auf den Rest in den Algorithmus selbst oder dahinter.

CStoll

Etwas besseres als "prüfe alle Zahlen, bis eine den Vorgaben entspricht" fällt mir auf Anhieb auch nicht ein, aber das kann man auch eleganter lösen als in deinem Beispiel (davon abgesehen, daß die Berechnungen, die du mit j anstellst, wenig mit der Aufgabenstellung zu tun haben):

j=4*(i/4)+3;
if(j<i) j+=4;
for(;!isPrim(j);j+=4);

(bei der Primzahl-Prüfung mußt du in der primtiven Variante nur Teiler bis zu sqrt(j) prüfen - und afaik gibt es inzwischen schnellere Verfahren dafür)

volkard

Ich würde es so aufschreiben:

#include <iostream>

int isFunnyPrime(int j){
    for(int t=3;t*t<=j;t+=2)
        if(j%t==0)
            return false;
    return true;
}

int findNextFunnyPrime(int i){
    int j=i-i%4+3;//int i=i|3;
    while(!isFunnyPrime(j))
        j+=4;
    return j;
}

int main(){
    using namespace std;
    for(;;){
        int i;
        cin>>i;
        cout<<findNextFunnyPrime(i)<<"\n\n";
    }
}

Wie man das Ent-C++-st, ist dann eine andere Frage.

Mir scheint, Deine Berechnung
j := j - 3
j := j / 4
verstehe ich gar nicht.

Äh ja mein Algorithmus war Banane, hab um ehrlich zu sein auch nicht wirklich darüber nachgedacht

Allerdings ist das KEINE Studienaufgabe, ich brauche das für eine eigene Hash-Datenstruktur, die ich schreiben will. Es geht um effizientes Sondieren bei Kollision.

Vielen Dank für die Tipps!

SeppJ

Darf ich vorschlagen ~~zu schummeln~~ die Aufgabenstellung kreativ zu interpretieren?

Du suchst dir eine möglichst große Primzahl mit der genannten Bedingung. Ist die Eingabe kleiner, dann gibst du diese aus. Ist die Eingabe größer, fällst du auf einen anderen Algorithmus zurück. Da nicht die kleinste Primzahl > i gesucht ist, kann man sich so für sehr viele Eingaben die Rechnung sparen.

Optimal wäre es natürlich, wenn die Eingabe irgendwie nach oben beschränkt wäre.\

edit: Ok, dadurch dass es keine Schulaufgabe ist, hätte sich dieser Vorschlag wohl erledigt .

edit2: Eine andere Methode die mir vorgeschwebt hätte, wäre mal zu gucken, ob Mersenne-Primzahlen die genannte Bedingung erfüllen können, dann hatte man einfach die nächsten Kandidaten prüfen können bis man eine Primzahl findet. Ist wohl auch für diese Aufgabe ungeeignet.

Was aber geeignet sein könnte: Du sagst, es wäre für eine Hashfunktion? Dann ist die Eingabemenge doch sicherlich nicht zu groß (32 Bit?) Da kannst du doch alle Primzahlen mit deiner Bedingung im Voraus suchen und im Programm einbauen. So viele können das doch nicht sein.

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.