백준 4984번: 베르트랑 공준[C++]

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

4948번: 베르트랑 공준

코드

#include <iostream>
using namespace std;

bool Prime_number[246913];

void find_Prime()
{
	Prime_number[1] = true;
	for(int i=2; i<246913; i++)
	{
		if(!Prime_number[i])
		{
			for(int j = i * 2; j < 246913; j += i)
			{
				Prime_number[j] = true;
			}
		}
	}
}

int main() {
	find_Prime();
	int n;
	cin >> n;
	
	while(n != 0)
	{
		int cnt = 0;
		for(int i = n+1; i <= n*2; i++)
		{
			if(!Prime_number[i]) cnt += 1;
		}
		cout << cnt << endl;
		cin >> n;
	}
	return 0;
}

 

설명

https://wonsang98.tistory.com/14?category=816114 

4948번: 베르트랑 공준(백준 C++)

작년에 풀었을때는 n부터 2n 안에 있는 수를 그냥 다 하나씩 소수 판별을 해서 풀었다.

그때 어지간히도 에라토스테네스의 체를 사용하기 귀찮았던거 같다.

그때는 그렇게 해도 시간초과가 발생하지 않았는데, 지금은 채점기준이 바뀌어서 그렇게하면 시간초과가 발생한다.

그래서 이번에는 문제에서 주어진 조건이 1 <= n <= 123456 이길래

배열의 길이가 123456 * 2 + 1인 배열을 하나 만들어주고

미리 에라토스테네스의 체를 사용해서 미리 소수 판별을 해놓고 시작했다.

그렇게 해서 그 범위내의 소수 개수만 세어주면 끝나는 문제.