Gay Prime

#include<iostream>
typedef long long ll;
using namespace std;
void segmented_prime(){
    const ll ok=2;
    ll p,i,j,n,a,b,t;
    scanf("%lld",&t);
    for(p=0;p<t;++p){
        scanf("%lld %lld", &a, &b);
        n=b-a+1;
        bool sieve[n];
        for(i=0;i<n;++i) sieve[i]=true;
        for(i=2;i*i<=b;++i){
            for(j=max(i*i,(a+(i-1))/i*i);j<=b;j+=i){
                sieve[j-a]=false;
            }
        }
        for(i=max(a,ok);i<=b;++i){
            if(sieve[i-a]) printf("%lld\n",i);
        }
    }
}
void eratosthenes(){
    ll i,p,j,n,t;
    cin>>t;
    for(p=0;p<t;++p){
        cin>>n;
        bool sieve[n+1];
        for(i=1;i<=n;++i) sieve[i]=true;
        for(i=2;i<=n;++i){
            if(sieve[i]){
                cout<<i<<endl;
                for(j=2*i;j<=n;j+=i) sieve[j]=false;
            }
        }
    }
}
void linear_sieve(){
    int i,j,n,pr[N];
    vector<int>ans;
    cin>>n;
    for(i=2;i<=n;++i){
        if(pr[i]==0){
            pr[i]=i;
            ans.push_back(i);
        }
        for(j=0;j<ans.size();++j){
            if(i*ans[j]>n) break;
            if(ans[j]>pr[i]) break;
            pr[i*ans[j]]=ans[j];
        }
    }
    for(i=0;i<ans.size();++i) cout<<ans[i]<<" ";
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//  segmented_prime();
//  eratosthenes();
//  linear_sieve();
}