본문 바로가기

알고리즘 관련/BOJ

BOJ)4948 베르트랑 공준

문제: icpc.me/4948


n~2n 사이의 소수의 개수를 출력하면 되는 문제이다.


에라토스테네스의 체로 소수들을 구해 준 뒤 파셜섬의 차를 구해주면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <cstdio>
#include <algorithm>
using namespace std;
bool p[270000];
int s[270000];
int n;
int main() {
    p[0= p[1= true;
    for (int i = 2; i <= 270000; i++) {
        if (p[i])continue;
        for (int j = i + i; j <= 270000; j += i) {
            p[j] = true;
        }
    }
    for (int i = 2; i <= 270000; i++) {
        if (!p[i])s[i]++;
        s[i] += s[i - 1];
    }
    scanf("%d"&n);
    while (n) {
        printf("%d\n", s[* n] - s[n]);
        scanf("%d"&n);
    }
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)13701 중복 제거  (0) 2017.01.06
BOJ)1647 도시 분할 계획  (0) 2017.01.06
BOJ)12842 튀김 소보루  (0) 2017.01.05
BOJ)13505 두수 XOR  (4) 2017.01.05
BOJ)12843 복수전공  (0) 2017.01.05