C++ / 백준 / 4948 / 베르트랑 공준

문제

 

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

4948번: 베르트랑 공준

문제풀이

 

소수의 개수를 구하는 문제이다.

0을 입력받기 전까지 계속 입력을 받으므로 소수를 미리 구하는 것이 좋아 보인다.

따라서 에라토스테네스의 체를 이용해 입력의 최댓값 123456 * 2인값까지 중 소수를 구한다.

 

	vector<bool>isPrime(246913, true);
	for (int idx = 2; idx <= sqrt(246912); ++idx) {
		for (int idx2 = 2; idx * idx2 <= 246912; ++idx2) {
			isPrime[idx * idx2] = false;
		}
	}

	vector<int>prime;
	for (int idx = 2; idx <= 246912; ++idx) {
		if (isPrime[idx] == true) {
			prime.push_back(idx);
		}
	}

 

에라토스테네스의 체 부분이다.

2*2부터 2*N까지

N*2부터 N*N까지 수를 구해 해당 숫자에 해당하는 부분을 false로 바꾼다. (해당 값은 N과 M으로 만들어진 수이므로 소수가 아니다)

 

그다음 prime라는 소수를 모아두는 벡터를 만들어 모두 push 한다.

 

	while (1) {
		cin >> N;
		if (N == 0) break;

		int N_left_idx(0), N_right_idx(0);
		N_left_idx = lower_bound(prime.begin(), prime.end(), N + 1) - prime.begin();
		N_right_idx = upper_bound(prime.begin(), prime.end(), 2 * N) - prime.begin();

		cout << N_right_idx - N_left_idx << '\n';
	}

 

소수를 모두 구했으면 반복문을 작성한다.

N이 0이면 종료되는 조건을 넣는다.

이분탐색인 lower_bound와 upper_bound를 이용해 N+1의 인덱스, 2*N을 넘어가는 인덱스를 구한다. (2*N+1 이상)

N+1부터 2*N의 개수를 구해야 하므로 upper_bound의 인덱스 - lower_bound의 인덱스 값을 빼면 답이 된다.

 

코드

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int N(0);

	vector<bool>isPrime(246913, true);
	for (int idx = 2; idx <= sqrt(246912); ++idx) {
		for (int idx2 = 2; idx * idx2 <= 246912; ++idx2) {
			isPrime[idx * idx2] = false;
		}
	}

	vector<int>prime;
	for (int idx = 2; idx <= 246912; ++idx) {
		if (isPrime[idx] == true) {
			prime.push_back(idx);
		}
	}

	while (1) {
		cin >> N;
		if (N == 0) break;

		int N_left_idx(0), N_right_idx(0);
		N_left_idx = lower_bound(prime.begin(), prime.end(), N + 1) - prime.begin();
		N_right_idx = upper_bound(prime.begin(), prime.end(), 2 * N) - prime.begin();

		cout << N_right_idx - N_left_idx << '\n';
	}
}