#include <iostream>
#include <ctime>
#include <bitset>

int main()
{
	const int n = 2000000;
	clock_t cstart = clock();
	std::bitset<n + 1> b;
	int count = 0;
	int i;
	for (i = 2; i <= n; ++i) {
		b.set(i);
	}
	i = 2;
	while (i * i <= n) {
		if (b.test(i)) {
			++count;
			int k = 2 * i;
			while (k <= n) {
				b.reset(k);
				k += i;
			}
		}
		++i;
	}
	while (i <= n) {
		if (b.test(i)) {
			++count;
		}
		++i;
	}
	clock_t cend = clock();
	double ms = 1000.0 * (cend - cstart) / CLOCKS_PER_SEC;
	std::cout << count << " total " << ms << " ms";
	system("pause");
    return 0;
}