백준 - 베르트랑 공준(4948)

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

4948번: 베르트랑 공준

 

베르트랑 공준

 

주어진 숫자 n의 n+1부터 2n 사이의 소수의 개수를 세는 문제이다.

 

제출한 코드는 아래와 같습니다.

 

#include <iostream>
using namespace std;
#define MAX_VALUE 300001

int arr[MAX_VALUE];

void getPrime()
{
	arr[1] = 0;
	for (int i = 2; i*i < MAX_VALUE; i++)
	{
		for (int j = i+i; j <= MAX_VALUE; j += i)
		{
			if (arr[j] == 1) arr[j] = 0;
		}
	}
}

int count(int n)
{
	int res = 0;
	for (int i = n+1; i <= 2 * n; ++i)
	{
		if (arr[i] == 1) res++;
	}
	return res;
}

int main(void)
{
	for (int i = 0; i < MAX_VALUE; ++i) arr[i] = 1;
	getPrime();
	int n;
	do
	{
		cin >> n;
		if (n == 0) break;
		cout << count(n) << endl;
	} while (n != 0);
}