Optimierung eines Primzahlberechners

Hallo, ich habe letztens einen Primzahlenberechnungsalgorithmus geschrieben der so aussieht:

[cpp]
#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;

int main (void)
{
bool marker;
DWORD Anfang = GetTickCount(); //Zur Berechnung der gebrauchten Zeit

for (int i=3; i<300000; i+=2) //Schleife, die alle ungeraden Zahlen
{ //durchgeht
marker = false;
double wurzel = i;
wurzel = sqrt(wurzel);

for (int k=2; k <= wurzel ; k++) //Schleife, die überprüft, ob es sich
{ //um eine Primzahl handelt
if (i % k == 0)
{
marker=true;
break;
}
}

if (marker == false)
{
cout << i << "\n";
}
}
DWORD Ende = GetTickCount();
DWORD Dauer = Ende-Anfang;
cout << "\n Zeit:" << Dauer << "Millisekunden\n" ;
system ("PAUSE");
}

Ich bin mir allerdings sicher, dass der noch nicht ausoptimiert ist, da lässt sich doch sicher noch Performance rausholen. Wer hätte da einen Vorschlag?

http://www.c-plusplus.net/forum/viewtopic-var-t-is-112808-and-start-is-10.html :schland::schland::schland::schland::schland::schland::schland::schland::schland::schland:

Sorry, hab das [/cpp]-Tag vergessen... hier nochmal der Code:

#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;

int main (void)
{ 
    bool marker;
    DWORD Anfang = GetTickCount();

    for (unsigned int i=3; i<100; i+=2) 
    { 
        marker = false;
        double wurzel = i;
        wurzel = sqrt(wurzel);

        for (int k=2; k <= wurzel ; k++)
        {
                if (i % k == 0)
                {
                                marker=true; 
                                break;
                }
        }

        if (marker == false)
        {
                cout << i << "\n";
        }
    }
    DWORD Ende = GetTickCount();
    DWORD Dauer = Ende-Anfang;
    cout << "\n Zeit:" << Dauer << "Millisekunden\n" ;
    system ("PAUSE");
}

Th

Du solltest, wenn möglich ein und denselben Datentyp für deine Berechnungen nehmen, z.B. nur 'int'.
Außerdem ist die folgende Anweisung noch optimierbar:

double wurzel = i;
wurzel = sqrt(wurzel);

Und du brauchst in der zweiten Schleife auch nur die ungeraden Zahlen prüfen, da 'i' ja niemals durch 2 teilbar ist.

Mein Vorschlag:

for (int i=3; i<100; i+=2)
    { 
        marker = false;
        int wurzel = (int)sqrt(i);

        for (int k=3; k <= wurzel; k+=2)
        {
                if (i % k == 0)
                {
                                marker=true; 
                                break;
                }
        }

        if (marker == false)
        {
                cout << i << "\n";
        }
    }