segmentedSieveR, C++ (gcc)

segmentedSieveR

#include<iostream>
#include<vector>
#include<cmath>
#include<cstring>
using namespace std;
void simpleSieve(int limit,vector<int> primes){
    bool mark[limit+1];
    memset(mark,true,sizeof(mark));
    int i,j;
           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<<" ";
                   primes.push_back[i];
               }
           }
}
void segmentedSieve(ll n){
    int limit=sqrt(n),i,j;
    vector<int>& primes;
    simpleSieve(limit,primes);
    bool mark[limit];
    memset(mark,true,sizeof(mark));
    int low=limit+1;
    int high=2*limit;
    while(low<=n){
        if(high>n)
            high=n;
        for(i=0;i<primes.size();i++){
            int base=(low/primes[i])*primes[i];
            if(base<low)
                base=base+primes[i];
            for(j=base;j<=high;j=j+primes[i])
                mark[j-low]=false;
        }
        for(i=0;i<high-low+1;i++){
            if(mark[i]==true)
                cout<<i+low<<" ";
        }
        low=low+limit;
        high=high+limit;
    }
}
int main(){
    segmentedSieve(10000);
}


run \| edit \| history \| help	0