#include <chrono>
#include <iostream>
#include <vector>

// Cherche les 400000 premiers nombres premiers avec le crible d'Eratosthene.
// La limite 6000000 est fixe: le 400000e nombre premier est 5800079.

int main() {
	const auto begin = std::chrono::steady_clock::now();

	const int targetCount = 400000;
	const int limit = 6000000;

	std::vector<unsigned char> isComposite(static_cast<std::size_t>(limit + 1), 0);
	std::vector<int> primes(static_cast<std::size_t>(targetCount), 0);

	for (int candidate = 2; candidate * candidate <= limit; ++candidate) {
		if (isComposite[static_cast<std::size_t>(candidate)] == 0) {
			for (int multiple = candidate * candidate; multiple <= limit; multiple += candidate) {
				isComposite[static_cast<std::size_t>(multiple)] = 1;
			}
		}
	}

	int count = 0;
	long long checksum = 0;
	for (int candidate = 2; candidate <= limit && count < targetCount; ++candidate) {
		if (isComposite[static_cast<std::size_t>(candidate)] == 0) {
			primes[static_cast<std::size_t>(count)] = candidate;
			checksum += candidate;
			++count;
		}
	}

	const int lastPrime = primes[static_cast<std::size_t>(count - 1)];

	std::cout << count << " primes\n";
	std::cout << "last = " << lastPrime << "\n";
	std::cout << "checksum = " << checksum << "\n";

	const auto end = std::chrono::steady_clock::now();
	const auto durationMs = std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count();
	std::cout << "Duration = " << durationMs << " ms\n";

	return 0;
}
