Baekjoon 4948 베르트랑 공준

Link https://www.acmicpc.net/problem/4948

결과 2544KB / 4 ms

언어 C++ 17

 

풀이

에라토스테네스의 체의 연장선

소수를 구하는게 중요한 문제

n이 123456 까지기 때문에 2부터 2n까지의 소수를 전부 구하면 된다.

소수를 구한 뒤 개수는 매 순간 반복문을 통해 구해도 문제가 없다.

 

소스코드

#include <iostream>

using namespace std;

const int MAX = 50000;

int prime[MAX];
int primeCount;

void eratos() {
	const int max = 123456 * 2 * 2;
	bool check[max + 1] = {true, true};

	for (int i = 2; i < max + 1; i++) {
		if (!check[i]) {
			prime[primeCount++] = i;
			for (int j = 2; i * j < max + 1; j++)
				check[i * j] = true;
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	eratos();

	int val; cin >> val;
	while (val) {
		int res = 0;
		
		int str = 0;
		while (prime[str] <= val)
			str++;

		for (int i = str; prime[i] <= (2 * val); i++)
			res++;

		cout << res << '\n';

		cin >> val;
	}

	return 0;
}