Segmented Sieve, C++ (gcc)

Segmented Sieve

//Segmented Sieve : generate prime no. less than N
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<ll> simpleSieve(ll limit, vector<ll> prime){
    bool isPrime[limit+1];
    memset(isPrime, true, sizeof(isPrime));
    for(int i=2;i*i<limit;++i){
        if(isPrime[i]){
            for(int j=i*i;j<limit;j+=i){
                isPrime[j] = false;
            }
        }
    }
    for(ll i=2;i<limit;++i){
        if(isPrime[i]){
            cout<<i<<" ";
            prime.push_back(i);
        }
    }
    return prime;
}

void segmentedSieve(ll n){
    ll limit = sqrt(n)+1;
    vector<ll> prime;
    prime = simpleSieve(limit,prime);
    ll low = limit;
    ll high = 2*limit;
    while(low<=n){
        if(high>=n){
            high = n;
        }
        bool isPrime[limit+1];
        memset(isPrime, true, sizeof(isPrime));
        for(ll i = 0;i<prime.size();i++){
            ll curPrime = prime[i];
            ll base = (low/curPrime) * curPrime;
            if(base<low){
                base+=curPrime;
            }
            for(ll j=base;j<high;j+=curPrime){
                isPrime[j-low] = false;
            }
            if(base==curPrime)
                isPrime[base-low] = true;
        }
        for(ll i=low;i<high;i++){
            if(isPrime[i-low]){
                cout<<i<<" ";
            }
        }
        low+=limit;
        high+=limit;
    }
}

int main(){
    ll n = 100;
    segmentedSieve(100);
    return 0;
}


run \| edit \| history \| help	0

Please log in to post a comment.

Advertise here.