baekjoon 4948

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

전역기념 문제풀이 ^^

---

Idea

알고리즘은
https://velog.io/@p3pwp3p/baekjoon-1929

요고랑 같고 조금만 생각하면 코드가 바로 나옴.
쉬우니 설명 생략
귀찮아서 그러는 거 아님.
진짜임

---

Code

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void) {
	int n, arr[247000] = { 0, };
	int cnt = 0;
	arr[1] = 1;

	while (1) {
		scanf("%d", &n);

		if (n == 0) {
			break;
		}

		for (int i = 2; i <= (2 * n); i++) {
			for (int j = 2; i * j <= (2 * n); j++) {
				arr[i * j] = 1;
			}
		}

		for (int i = (n + 1); i <= (2 * n); i++) {
			if (arr[i] == 0) {
				cnt++;
			}
		}
		printf("%d\n", cnt);
		cnt = 0;
	}

	return 0;
}

EZ