Algorithmus nächst höhere Primzahl

hi

eigentlich banal, aber ich komm nicht drauf.
ich suche einen algorithmus(c-code) der für eine gegebene zahl die nächst höhere primzahl berechnet. hat wer spontan was auf lager ?
achja, es darf kein boolean verwendet werden.danke

pain

Ich weiß es.
Hatten wir vor kurzem auch schon. Programmieren darfst Du aber selber.

Du gehst einfach davon aus, dass alle vielfachen einer Primzahl keine Primzahlen sind (1 kommt in diese Rechnung nicht mit rein)
Der Rest ist automatisch Primzahl.
Du fängst bei 2 an. 4 6 8 10 .. sind keine Primzahlen
3 ist noch nicht markiert -> Primzahl 6 9 12 15 .. keine Primzahlen
4 schon markiert
5 Primzahl 10 15 20 25 30 .. keine Primzahlen
6 schon markiert
7 Primzahl 14 21 27 35 .. keine P.
...

und so weiter..
viel spaß beim coden.

volkard

//Zitat: "Rather than divide by just the primes, it is sometimes 
//more practical to divide by 2, 3 and 5; then by all the numbers 
//congruent to 1, 7, 11, 13, 17, 19, 23, and 29 modulo 30--again 
//stopping when you reach the square root. This type of factorization 
//is sometimes called wheel factorization. Look in most any elementary 
//text on number theory for information about these tests. 
//Quelle: http://www.utm.edu/research/primes/prove/prove2.html 

//Die Idee, daß Primzahlen-Kandidaten p nur dann überhaupt als 
//Primzahlen in Frage kommen, wenn p mod 30 nicht durch 2,3,5 
//teilbar ist, wird in den folgenden Verfahren öfters zur Anwendung 
//kommen. Bitte behalten Sie diesen Satz stehts im Gedächtnis!

//Position der nächsten Primzahl
u32 firstPrimeNext[11]={2,2,3,5,5,7,7,11,11,11,11};

//Offset zur nächstmöglichen Primzahlenposition
u32 diffPrime[30]={1,6,5,4,3,2,1,4,3,2,1,2,1,4,3,2,1,2,1,4,3,2,1,6,5,4,3,2,1,2};
//Selber Offset zyklisch in Z30 erspart: if(m>30)m-=30
//Zweck: Sprünge sind auf modernen Prozessoren zu teuer.
u32 diffPrimeM[30]={1,6,5,4,3,2,1,4,3,2,1,2,1,4,3,2,1,2,1,4,3,2,1,6,5,4,3,2,1,2-30};
//1.073
u32 nextPrime(u32 last)
{
    if(last<11) return firstPrimeNext[last];
    u32 p=last;
    u32 mp=p%30;
    do
    {
        p+=diffPrime[mp];
        mp+=diffPrimeM[mp];
    }while(!isPrimeCheckFactorsAbove5(p));
    return p;
};

die isPrimeCheckFactorsAbove5(p) sollte offensichtlich sein, zum beispiel erstmal trial division. laß dich nicht veräppeln und zu nem sieb bringen. außer, deine aufgabe war es eh, ne liste von primzahlen austzgeben, statt nur die nächste zu finden.

hi

erstmal danke für die antworten.das das im prinzip simple ist -> klar, aber gerade deswegen kommt man nicht drauf. hab natürlich selber was versucht ;-).
da is aber irgendwo irgendein fehler drinne den ich ums verrecken nicht sehe.ich behaupte aber das das theoretisch richtig ist. es kommt weder auf effizienz noch sonst was an.simple as possible:

int prim (int wert)
{ 

    int dummy1 = wert;
   int dummy2 = wert+1;

    for (int j = dummy1; dummy1 <= 100;dummy1++)
   {
        for (int i=4; i<=dummy1+1;i++)
        {
         if (dummy1%i == 0)
         {
            if (i == dummy2)
            {               
               wert = i;
               j = 100;
            }
         }
        }
    }

   return(wert);

}

Prinzipieller ablauf sollte klar sein. habe ne zahl gegeben und prüfe für alle vorgänger ob der rest null ist. dann halt test ob wenn null gleich der zu testenden zahl ist, ansonsten weitergehen. muß mir nur noch was einfallen lassen wie ich zahlen 1-3 abfange. ich mein 3 else-if würdens ja eigentlich auch tun ;-).so denn vielleicht seht ihr mein fehler. danke nochma.

pain

ps: mal abgesehen davon das ich mich gra dnicht einlogen kann und somit auch den beitrag nicht editieren kann, is da ein fehler drinne.hier der richtige:

int prim (int wert)
{ 

    for (int j = wert; wert <= 100;wert++)
    {
          for (int i=4; i<=wert+1;i++)
          {
            if (wert%i == 0)
            {
                if (i == wert)
                {                   
                    wert = i;
                    j = 100;
                }
            }
          }
    }

    return(wert);

}

irgendwas is mit der abbruchbedingung faul, aber mir fällt nix anderes ein wenn ich kein boolean verwenden darf.

pain

-bg-

Die zu verwendende Methode hängt vom Zahlenbereich ab.
Hab mir mal ein Programm geschrieben, dass alle Primzahlen bis 2^32-1 ermittelt mit der klassischen Methode (dividieren durch alle gefundenen Primzahlen bis maximal zur Wurzel). Hat ewig gedauert und hatte nacher ne schön riesige File. damit kann mensch dass nun sehr ellegant machen.
aber bei größerern Zahlen, würde ich raten mit div. Primzahltests zu arbeiten (Rabin-Miller, solovay-Strassen).

mfg
-bg-