POJ-Prime Gap 소수 선별 + 2점 찾기

5338 단어 이분 검색
한 개의 수를 연속 구간에 세어라. 이 구간은 모두 화수의 길이이다.
코드는 다음과 같습니다.
#include <cstring>

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#define MAXN 1300000

using namespace std;



int p[MAXN+5], rec[100005], N;



void pre()

{

    int k;

    for (int i = 4; i <= MAXN; i += 2) {

        p[i] = 1;

    }    

    for (int i = 3; i <= 1141; i += 2) {

        if (!p[i]) {

            k = 2 * i;

            for (int j = i * i; j <= MAXN; j += k) {

                p[j] = 1;    

            }    

        }

    }

    for (int i = 2, j = 0; j <= 100000; ++i) {

        if (!p[i]) {

            rec[++j] = i;

        }

    }

}



int bsearch(int l, int r, int x, int f)

{

    int mid;

    while (l <= r) {

        mid = (l + r) >> 1;

        if (x < rec[mid]) {

            r = mid - 1;

        }

        else {

            l = mid + 1;

        }

    }    

    if (f == 1) {

        return rec[r];

    }

    else {

        return rec[l];

    }

}



int main()

{

    pre();

    int l, r;

    while (scanf("%d", &N), N) {

        if (!p[N]) {

            puts("0");

            continue;

        }

        l = bsearch(1, 100000, N, 1);

        r = bsearch(1, 100000, N, 2);

        printf("%d
", r - l); } return 0; }

좋은 웹페이지 즐겨찾기