Segmented_sieve

#include"bits/stdc++.h"
using namespace std;
#define MAX 1000000000
#define MS1(x) memset(x,1,sizeof(x))
#define ll long long
#define REP(i,n) FOR(i,0,(int)n-1)
int sq1 = sqrt(MAX);
int sq2 = sqrt(sq1);
char prime[MAX+5];


void seiv(){

	MS1(prime);
	ll int i, j;
	prime[0] = prime[1] = 0;

	for (i = 2; i<=sq2; i++){
		if (prime[i]){
			for (j = i*i; j<=sq1; j += i){
				if (prime[j])
					prime[j] = 0;
			}
		}
	}
}

void segmentedSeiv(int a, int b){

	int lim = sqrt(b);
	int i, j;
	for (i = 2; i <= lim; i++){
		if (prime[i]){
			for (j = a - a%i; j <= b; j += i)
				if (j>=a && prime[j] && j!=i)
					prime[j] = 0;
		}
	}

}

int main(){

	seiv();
	int t, n,m,i;
	scanf("%d", &t);
	REP(i, t){
		scanf("%d%d", &m, &n);
		if (n>sq2)
			segmentedSeiv(m, n);
		FOR(i,m,n)
			if (prime[i])
				printf("%d\n", i);
		printf("\n");
	}
	return 0;
}