segmented_seive.c

#include <stdio.h>
#include <string.h>
#define SIZE 100001

void seive(int range[], int prime[], int *prime_size)
{
    long long int i, j;
    range[0] = range[1] = 1;
    for(i=2; i<SIZE; ++i) {
        if(range[i] == 0) { 
            prime[(*prime_size)++] = i;
            for(j=i*i; j<SIZE; j+=i) {
                range[j] = 1; 
            }
        }
    }
}

int main(void)
{
    int range[SIZE], prime[SIZE], prime_size = 0;
    memset(range, 0, sizeof range);
    seive(range, prime, &prime_size);

    int t, start, end, i, j, number;
    scanf("%d", &t);

    while(t--) {
        scanf("%d%d", &start, &end);

        for(i=start; i<=end && i<SIZE; ++i) {
            if(range[i] == 0) {
                printf("%d\n", i);
            }
        }
        if(end >= SIZE) {
            memset(range, 0, sizeof range);
            start = start > SIZE ? start : SIZE;
            for(i=0; i<prime_size; ++i) {
                number = (start/prime[i]) * prime[i];
                number = number < start ? number + prime[i] : number;
                for(j=number; j<=end; j+=prime[i]) {
                    range[j-start] = 1;
                }
            }
            for(i=start; i<=end; ++i) {
                if(range[i-start] == 0) {
                    printf("%d\n", i);
                }
            }
        }
        printf("\n");
    }

    return 0;
}