[백준 / BOJ] 4948번 베르트랑 공준 (C++, Python)

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

4948번: 베르트랑 공준

---

문제

---

문제 풀이

소수를 구하는 이전 문제들과 비슷한 맥락이지만 일일이 소수를 판별하는 알고리즘을 사용하면 시간 초과가 난다. 에라토스테네스의 체를 이용해야 한다. 잘 설명해주신 분이 있어 링크를 첨부한다.

 

https://maramarathon.tistory.com/39

소수 판별 알고리즘과 에라토스테네스의 체

 

 

C++ 코드 전문

	#include <iostream>
	#include <algorithm>
	using namespace std;
	bool arr[246913];
	void isPrime() {
	int i = 2;
	arr[0] = false;
	arr[1] = false;
	while (i <= 246912) {
	if (arr[i])
	for (int j = i + i; j <= 246912; j += i)
	if (arr[j])
	arr[j] = false;
	i++;
	}
	}
	int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int N;
	cin >> N;
	fill(arr, arr + 246913, true);
	isPrime();
	while (N) {
	int res = 0;
	for (int i = N + 1; i <= 2 * N; ++i)
	if (arr[i])
	res++;
	cout << res << "\n";
	cin >> N;
	}
	return 0;
	}

view raw 4948_베르트랑 공준 (22.04.08 성공).cpp hosted with ❤ by GitHub

 

Python 코드 전문

	arr = [False, False] + [True] * (246912 - 1)
	i = 2
	# 에라토스테네스의 체
	while i <= 246912:
	if arr[i]: # 지워나가는 과정
	for j in range(i + i, 246912 + 1, i):
	if arr[j]:
	arr[j] = False
	i += 1
	while True:
	N = int(input())
	if (N == 0):
	break
	res = 0
	for i in range(N + 1, 2 * N + 1):
	if (arr[i]):
	res += 1
	print(res)

view raw 4948_베르트랑 공준 (22.04.08 성공).py hosted with ❤ by GitHub

 

소감