Primzahlen herausbekommen!

[revelation]

Wollte mal ausprobieren ob es noch schneller geht - und JA, es geht!

Hier der Code:

__inline int JSqrt(float number)
{
    long i;
    float x2, y;
    const float threehalfs = 1.5f;
    
    x2 = number * 0.5f;
    y  = number;
    i  = * (long *) &y;      // evil floating point bit level hacking
    i  = 0x5f3759df - (i >> 1);             // what the fuck?
    y  = * (float *) &i;
    y  = y * (threehalfs - (x2 * y * y));   // 1st iteration
    //y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed
    
    return (int) (1/y);
}

__inline bool is_prim(int zahl)
{
    bool isprim = true;
    int sqr_zahl = JSqrt((float) zahl);
    
    for(int i = 2; i <= sqr_zahl; ++i)
        if(zahl % i == 0)
        {
            isprim = false;
            break;
        }
    return isprim;        
}

int get_prim_number(int num)
{    
    int akt_num = 1, prim_count = 2;
    
    if(num == 1)
       return 2;

    while(prim_count <= num)
    {
        akt_num += 2;
        
        if(is_prim(akt_num))
            ++prim_count;                   
    }
    
    return akt_num;
}

Die JSqrt-Funktion habe ich mir von dem netten Herrn Carmack geborgt (aus der Quake-Engine. Leider entzieht sich ihre Funktionsweise meiner Kenntniss ). Der Code ist aber auch mit der normalen sqrt-funktion schneller!

Gruß
Johannes

PS: Ich weiß, dass sich mein Code eigentlich nur an zwei Stellen wesentlich unterscheidet:

for (iTeiler = 2; iTeiler * iTeiler < iKandidat; ++iTeiler)

->

int sqr_zahl = JSqrt((float) zahl);
    
for(int i = 2; i <= sqr_zahl; ++i)

es muss nur einmal dir Wurzel gezogen werden, anstatt immer das Produkt des Zählvariablen zu berechnen.

Und

++iKandidat;

->

akt_num += 2;

Da es außer der 2 sowiso keine geraden Primzahlen gibt, reicht es die ungeraden zu prüfen - die hälfte der Schleifendurchläufe wird eingespart.