bool p[1001000];
for (int i = 0; i < 1000010; i++)
    p[i] = true;
p[1] = false;
for (int i = 2; i <= 1000010; i++)
    if (p[i])
        for (int j = 2 * i; j <= 1000010; j += i)
            p[j] = false;
//если p[x] == true, то x – простое