[C언어]백준 4948번: 베르트랑 공준

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

4948번: 베르트랑 공준

---

• 문제

---

• 문제풀이

기본적으로 에라토스테네스의 체를 활용하는데 문제에서 N보다 크고 2N보다 작거나 같은 소수의 개수를 구하라고 했다. 처음에 N부터 시작해서 몇번 틀렸었다.

 

[알고리즘] 에라토스테네스의 체

---

• 코드 1

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <math.h>
#define _CRT_SECURE_NO_WARNINGS

int a[123456*2+1];
int number = 123456*2+1;
void Sieve() {
	for (int i = 2; i <= number; i++) {
		a[i] = i;
	}
	for (int i = 2; i <= number; i++) {
		if (a[i] == 0) continue; 
		for (int j = 2 * i; j <= number; j += i) {
			a[j] = 0;
		}
	}
}
int main(void)
{
	int input;
	Sieve();
	while (true) {
		int count = 0;
		scanf("%d", &input);
		if (input == 1) {
			printf("%d\n", 1);
		}
		else if (input == 0) {
			break;
		}
		else{
			for (int i = input+1; i <= input*2; i++) {
				if (a[i] != 0) {
					count++;
				}
			}
			printf("%d\n", count);
		}
		
	}

}

 

---

• 후기

문제를 잘 읽자