[BOJ] 4948번 : 베르트랑 공준

1. problem : 

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

 

2. solution 1:

#include <bits/stdc++.h>
using namespace std;
const int val = 123456 * 2;

vector<int> eratos(int a) {
	vector<int> primes; 
	vector<int> nums(a + 1, true); 
	nums[1] = false;
	for (int i = 2; i * i <= a; i++) {
		if (!nums[i]) continue; 
		for (int j = i * i; j <= a; j += i) {
			nums[j] = false;
		}
	}
	for (int i = 2; i <= a; i++) {
		if (nums[i]) primes.push_back(i);
	}
	return primes;
}
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	//eratos sieve  
	vector<int> primes = eratos(val);
	while (true) {
		int n; 
		cin >> n; 
		if (n == 0) return 0; 
		int cnt = 0; 
		for (auto p : primes) {
			if (n < p && p <= 2 * n) cnt++;
		}
		cout << cnt << '\n';
	}
}

에라토스테네스의 체를 이용해 풀었다. 공식이 기억나지 않아, 저번에 작성했던 글을 참조했다. 

 

3. solution 2 :

// Authored by : jihwan0123
// Co-authored by : -
// http://boj.kr/1e50fd9692f645148720fa5f61929dba
#include <bits/stdc++.h>
using namespace std;
const int m = 123456 * 2;
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  vector<bool> state(m + 1, true);
  state[1] = false;
  for (int i=2; i*i<=m; i++){
    if (!state[i]) continue;
    for (int j=i*i; j<=m; j+=i)
      state[j] = false;
  }
  int n, cnt;
  while(1){
    cin >> n;
    if (n==0) break;
    cnt = 0;
    for (int i=n+1; i<=2*n; i++)
      if (state[i]) cnt++;
    cout << cnt << '\n';
  }
}

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x12/solutions/4948.cpp

basic-algo-lecture/0x12/solutions/4948.cpp at master · encrypted-def/basic-algo-lecture