Segmented Seive

#include<bits/stdc++.h>
#define N 10000000
#define ll unsigned long long int
using namespace std;
int p[N+1];
vector<int>a;

void prime()
{
    ll i, j;
    ll l = sqrt(N);
    p[0] = p[1] = 1;
    a.push_back(2);
    for(i=4; i<=N; i+=2)
        p[i] = 1;
    for(i=3; i<=N; i+=2)
    {
        if(p[i] == 0)
        {
            a.push_back(i);
            if(i<=l)
            {
                for(j=i*i; j<=N; j+=i*2)
                {
                    p[j] = 1;
                }
            }
        }
    }
}

vector<ll>b;
void segseive(ll l, ll r)
{
    ll i, j;
    ll n = r-l+1;
    bool s[n];
    for(i=0; i<n; i++)
        s[i] = true;
    if(l == 1)
        s[0] = false;
    for(i=0; a[i] * a[i] <=r; i++)
    {
        ll cp = a[i];
        ll base = (l/cp) * cp;
        if(base < l)
            base += cp;
        for(j=base; j<=r; j+=cp)
            s[j-l] = false;
        if(base == cp)
            s[base - l] = true;
    }
    for(i=0; i<n; i++)
        if(s[i] == true)
            b.push_back(l+i);
}

int main()
{

    prime();
    segseive(1000000000100, 1000000000200);

    for(ll i = 0; i<b.size(); i++)
        cout << b[i] << endl;

    return 0;
}