#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>

class BoolArray32 {
	int* values;
	int mask0[32], mask1[32];

public:

	BoolArray32(int _size)
	{
		values = (int*) calloc((_size - 1) / 32 + 1, sizeof(int));

		for (int i = 0; i < 32; i++)
		{
			mask1[i] = (1 << i);
			mask0[i] = ~mask1[i];
		}
	}

	~BoolArray32() {
		free(values);
	}

	bool Get(int _index)
	{
		return 0 != (values[_index >> 5] & mask1[_index & 31]);
	}

	void Set(int _index, bool _value)
	{
		if (_value)
			values[_index >> 5] |= mask1[_index & 31];
		else
			values[_index >> 5] &= mask0[_index & 31];
	}
};

int64_t Eratosfen(int len) {
	printf("Test %d" , len);
	clock_t t = clock();
	int64_t sum = 0;
	BoolArray32 s(len);
	s.Set(0, true);
	s.Set(1, true);
	int found = 0;
	while (found < len) {
		sum += found;
		while (found < len && s.Get(found)) found++; // Следующее простое
		for (int i = found; i < len; i += found) s.Set(i, true);
	}
	printf(" result %lld Time %d ms\n", sum, clock() - t);
	return sum;
}

int main(int argc, char**argv)
{
	Eratosfen(1000000);
	Eratosfen(2000000);
	Eratosfen(4000000);
	Eratosfen(8000000);
	Eratosfen(10000000);
	Eratosfen(20000000);
	Eratosfen(40000000);
	Eratosfen(80000000);
	Eratosfen(100000000);
	Eratosfen(200000000);
	Eratosfen(400000000);
	Eratosfen(800000000);
	return 0;
}