Ранее писал о простых числах. Нахождение простых чисел решетом эратосфена на C# тут сейчас же тоже самое на C++:
#include "stdafx.h"
#include <math.h>
void erato(int number)
{
bool *a = new bool[number];
for (int i = 0; i < number; i++)
a[i] = true;
for (int i = 0; i < number; i++)
{
for (int i = 2; i < sqrt(number*1.0) + 1; ++i)
{
if (a[i])
{
for (int j = i * i; j < number; j += i)
{
a[j] = false;
}
}
}
}
for (int i = 2; i < number; i++)
{
if (a[i])
printf("%d ", i);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int n;
scanf("%d", &n);
erato(n);
return 0;
}