Using Sieve of Eratosthenes with lesser space complexity

This method is called as Segmented Sieve.

The idea of segmented sieve is to divide the range [0..n-1] in different segments and compute primes in all segments one by one. This algorithm first uses Simple Sieve to find primes smaller than or equal to √(n). 

Look I would really like to write about the concept of Segmented Sieve but I think the number of the viewers of my page is few, so what I am gonna do is post some links and code.

Go through this link

#include <iostream>
#include <math.h>
#include <vector>
using namespace std;
void simple_sieve(vector<int> &vec,int num)
{
int range = sqrt(num);
vector<bool>mark(range+1,true);
for(int i =2;i<=sqrt(range);i++) //checking prime numbers <= number^1/2
{
if(mark[i]==true)
{
for(int j=i*2;j<=range;j= j+i)
{
mark[j] = false;
}
}
}
for(int i=2;i<=range;i++)
{
if(mark[i]==true)
{
vec.push_back(i);
}
}

}

void  segmented_sieve(vector<int> &prime , int num)
{
simple_sieve(prime,num);
int lower_range = sqrt(num);
int limit  = lower_range;
int higher_range = 2*lower_range;


while(lower_range<num &&higher_range<=num)
{
vector<bool>mark(limit+1,true);
for(int i =0;i<prime.size();i++)
{
int k = (lower_range/prime[i])*prime[i];
if(k<lower_range){k = k+ prime[i];}
for(int j=k;j<=higher_range;j = j+prime[i])
{
mark[j-lower_range] = false;

}
}
for(int i=lower_range;i<=higher_range;i++)
{
if(mark[i-lower_range]==true)
{
prime.push_back(i);
}
}
lower_range = lower_range + limit;
higher_range = higher_range + limit;
if(higher_range>num){higher_range = num;}
}

}

int main()
{
int num = 1000;
std::vector<int> prime;
segmented_sieve(prime,num);
for (int i = 0; i < prime.size(); ++i)
{
cout<<prime[i]<<endl;
}
}

The usual time complexity of this algorithm is O(N log (log N)).

If you want to perform the Sieve of Eratosthenes in a complexity of O(n) , 

go through This link