[BOJ] 백준 4948 베르트랑 공준

Approach

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

 

[N, 2N] 사이의 소수 개수를 구하는 문제이다.

입력 개수가 많을 수 있기 때문에

효율적으로 소수 개수를 구할 수 있는 "에라토스테네스의 체" 개념을 이용한다.

 

 

<소수를 구하는 방법>

• 소수 (Prime Number) 찾기 - 1 (Basic)

• 소수 (Prime Number) 찾기 - 2

• 소수 (Prime Number) 찾기 - 3 (에라토스테네스의 체)

---

#include <stdio.h>

const int MAX_N = (123456 * 2) + 2;
int prime[MAX_N] = { 1, 1, 0, };
int N, ans;

int main()
{
	// freopen("input.txt", "r", stdin);
	for(int i = 2; i < MAX_N / i; i++)
	{
		if (prime[i]) continue;
		
		for (int j = i * i; j < MAX_N; j += i)
		{
			if (j % i == 0) prime[j] = 1;
		}
	}
	
	scanf("%d", &N);
	while (N != 0) // 마지막 입력까지 진행
	{
		ans = 0;
		for (int i = N + 1; i <= N * 2; i++)
		{
			if (!prime[i]) ans++;
		}

		printf("%d\n", ans);
		scanf("%d", &N); // 새로운 N 입력
	}
}