segmentedSieveD, C++ (gcc)

segmentedSieveD

#include<iostream>
#include<cmath>
#include<vector>
#include<cstring>
typedef long long ll;
using namespace std;

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

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


run \| edit \| history \| help	0