백준 4948 베르트랑 공준

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다.

 

이 문제는 주어진 n에 대하여 n보다 크고 2n보다 작거나 같은 범위의 소수의 개수를 출력하는 문제입니다.

 

저는 에라토스테네스의 체를 이용하여 2n보다 작은 소수를 모두 찾고 n과 2n사이의 소수의 개수를 카운트해서 풀었습니다.

 

다음은 코드입니다.

 

#include <iostream>
//에라토스테네스의 체 

using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int N = 1;
	bool arr[300000];
	 
	
	while(1) {
		fill_n(arr, 300000, true);
		arr[0] = false;
		arr[1] = false;
		int num = 0;
		cin >> N;
		
		if(N == 0)
			break;
	
	for(int i =2; i <= 2*N; i++) {
			if(arr[i]) {
				for(int j = i+i; j <= 2*N; j+=i)
					arr[j] = false;
			}
		}
	
	for(int i = N+1; i <= 2*N; i++)
		if(arr[i])
			num++;
		
		cout << num << '\n';	
	}
	return 0;
}