Массив чисел позволяет искать простые числа до миллиона.
Очевидно, что это крайне неэффективный по памяти алгоритм.
#include "stdafx.h"
#include <iostream>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
const int ds = 1000000;
bool m[ds + 1];
for (int i = 0; i <= ds; i++) m[i] = true;
int x;
cin >> x;
int p = 2;
while (p * p < x) {
for (int i = p * p; i <= x; i += p) {
m[i] = false;
}
for (int i = p + 1; i <= x; i++) {
if (m[i]) {
p = i;
break;
}
}
}
cout << p << endl;
for (int i = 2; i <= x; i++) {
if (m[i]) {
cout << i << "\t";
}
}
cout << endl;
system("pause");
return 0;
}