참 오랜만에 백준을 푼 것 같다.
https://www.acmicpc.net/problem/4948
베르트랑 공준에 관한 문제. 임의의 자연수 n에 대해 n ~ 2n사이에 소수는 적어도 하나가 존재한다는 이론이다. 현재 완전히 증명되어있는 이론.
소수문제를 풀면서 에라토스테네스의 체를 한번 구현해 놓으니 거의 모든 소수문제가 복붙수준으로 풀리고 있다.
이 문제도 에라토스테네스의 체를 한번 만들어 놓은 후에, 범위에 따라 개수를 세면 되는 문제.
#include <stdio.h>
#define MAX_SIZE 123456 * 2 + 1
int main () {
int seive[MAX_SIZE] = {0,};
for (int i = 2; i < MAX_SIZE; i++) {
seive[i] = 1;
}
for (int i = 2; i < MAX_SIZE; i++) {
if (seive[i]) {
for (int p = 2; i*p < MAX_SIZE; p++) {
seive[i*p] = 0;
}
}
}
int n = 1;
int cnt = 0;
while (1) {
cnt = 0;
scanf("%d", &n);
if (!n) break; //n이 0이면 break
for (int i = n + 1; i <= 2 * n; i++) {
if (seive[i]) cnt++;
}
printf("%d\n", cnt);
}
return 0;
}
'coding_test > BAEKJOON' 카테고리의 다른 글
백준 2869번 C언어 풀이 (0) | 2021.09.09 |
---|---|
백준 1193번 C언어 풀이 (0) | 2021.09.09 |
백준 2775번 C언어 풀이 (0) | 2021.08.30 |
백준 15829번 C언어 풀이 (0) | 2021.08.27 |
백준 11050번 C언어 풀이 (0) | 2021.08.27 |