[백준] [C++] 4948 베르트랑 공준

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

4948번: 베르트랑 공준

 

 

이 문제는 1929번 문제와 크게 다르지 않다.

범위만 n~2n으로 바뀌었을 뿐

1929번 풀 때는 삽질을 엄청나게 했는데, 1929 풀고 나니 이 문제는 쉽게 풀렸다

 

 

https://katteniiki.tistory.com/23

[백준] [C++] 1929 소수 구하기, 에라토스테네스의 체

 

 

 

#include <iostream>

const int Max = 123456 * 2;

int main()
{
	bool arr[Max + 1] = { false }; //false면 소수
	arr[1] = true;

	for (int i = 2; i * i <= Max; ++i)
	{
		if (!arr[i]) //i의 배수 지우기
		{
			for (int j = 2; i * j <= Max; ++j) arr[i * j] = true;
		}
	}

	int ch;
	std::cin >> ch;
	while (ch) //0을 입력하면 종료
	{
		int count = 0;
		for (int i = ch + 1; i <= 2 * ch; ++i)
		{
			if (!arr[i]) ++count; //false의 개수 세기
		}
		std::cout << count << '\n';
        
		std::cin >> ch;
	}
}

 

 

 

 

미리 범위 내의 소수를 다 판별하는 것 말고... 다른 방법이 있을 것 같기도 한데 모르겠다.