okay, motivation (don't think i'm a looser 'cause i'm sitting here on friday night, having nothing to do but imposing such a contest upon you, i'll go out later on ).

my "brute-force"-entry (1), short and dirty, just to make you eager to show me you can do better:

Code:

---

#include <iostream>
#include <cmath>
#include <bitset>

#include <windows.h>

typedef unsigned int uint;

bool check(uint n)
{
    uint lim = (uint)sqrt((double)n);

    for (uint i = 2; i <= lim; i ++)
        if (!(n%i)) return false;

    return true;
}


int _tmain(int argc, _TCHAR* argv[])
{
    std::bitset<4194304> bits;
    uint start = GetTickCount();

    std::cout << "starting..." << std::endl;

    for (uint i = 2; i <= 4194304; i ++)
        bits[i-1] = check(i);

    std::cout << "finished." << std::endl
        << (float)(GetTickCount() - start)/1000 << " seconds needed." << std::endl;

    return 0;
}

---

execution time is somewhat less than one second, so i took fourth the size. since the execution time t(n) ~ sqrt(n), and the output shows 10.5 seconds, the time needed for 1 048 576 primes is

t = 10.5 seconds / (4^2) = 0.66 seconds (approx.)

the code shows you how to measure the time easily, if you didn't know already.

joey.