4948번 : 베르트랑 공준

N보다 크고 2N보다 작거나 같은 소수는는 적어도 하나 존재한다.

 

#include <iostream>
#include <vector>

int GetPrimeCount(const std::vector<bool>& primeIndex, const int N, const int M)
{
	int count = 0;

	for (size_t i = N + 1; i <= M; i++)
	{
		if (primeIndex[i] == false)
			continue;
		count++;
	}

	return count;
}

int main(void)
{
	std::cout.tie(NULL);
	std::cin.tie(NULL);
	std::cin.sync_with_stdio(false);

	std::vector<int> input;

	int maximum = 0;
	while (true)
	{

		int N;
		std::cin >> N;

		if (N == 0)
			break;

		if (N > maximum)
			maximum = N;

		input.emplace_back(N);

	}

	std::vector<bool> index((maximum * 2) + 1, true);

	index[0] = false;
	index[1] = false;

	for (int i = 2; i <= (maximum * 2); i++)
	{
		for (int j = 2; j * i <= (maximum * 2); j++)
		{
			index[j * i] = false;
		}
	}

	for (auto& inputNum : input)
	{
		auto primeCount = GetPrimeCount(index, inputNum, inputNum * 2);
		std::cout << primeCount << "\n";
	}



	return 0;
}

4948번: 베르트랑 공준 (acmicpc.net)

4948번: 베르트랑 공준