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

pointer arithmetic of an Array and passing a 2D array to a function

Before moving further let's see how a one-dimensional array is stored in a computer memory.
For example, let an array:
                         A = [   3   ][   4   ][   5   ][   6   ][   7   ]      -> value stored in an integer array
                                 200    204     208    212     216         -> these are the address of the memory of the array. As it is an integer array each element has a storage of 4 bytes.

To declare a pointer to a one-dimensional array we simply write:

    int *ptr = A; 
this pointer ptr points to the starting block of the array A. Also, the name of the array i.e A just returns a pointer to the first element of the array.
With the pointer declared we can use pointer arithmetic and dereferencing to access the address and elements of the array.
for example,

print ptr  will give output = 200

print *ptr will give output = 3, i.e the value stored at that memory location (this is called as                                                                                                                                           dereferencing )
print *(ptr +2)  will give us the output 5  as ptr is a pointer to an integer so increasing ptr two times will enhance it to further 8 bytes.

print (ptr +2)  = 208

The language flexibility allows us to use the name of the array as a pointer. Therefore instead of using ptr we can directly use A.
i.e ,

print A = 200
print *A = 3
print *(A+2) = 5
print A+2 = 208

in short,
*(A+i) is same as A[i]
and (A+i) is same as &A[i]

Therefore, ptr = A  but A != ptr .

we can pass a one-dimensional array  in a function as follows:

void myfunction (int *arr)
{
       int n = arr.size();
       cout<<arr[i];
}

int main()
{
   int arr = {1,2,3,4,5,6};
   myfunction(arr);
}

We can do the same thing in a multi-dimensional array. What does it mean when we say multi-dimensional array? A multi-dimensional array is an array of array.
 Let's talk about the two-dimensional array:

Suppose we have a 2-D array:
 B[2][3] = [  [ 2 , 3, 6 ] , [ 4 , 5  ,8  ] ]
                     400             412            -> memory address of the arrays.
Now each element  B[0] and B[1] is an array of integers consisting of three integers each. Hence each block would have a size of 3*4 bytes i.e 12 bytes. Therefore B[0] contains the starting address of the first array  i.e 400  and B[1] contains the starting address of the second array i.e 412.

if we  write,
int *ptr = B ; this will return an error because ptr is a pointer to integer but B is a pointer to a 1-D array of integers.
We can define a pointer to 1-D array of three integers like this:
int (*ptr)[3] = B ;

print B  is same as print (B+0)  and from the above-given statement in 1-D array, (B+i) = &B[i]
 Therefore print B = print  &B[0]  = 400 .

Similarly,
print *B is same as print B[0]  which is equal to a variable name of an array as B[0] is itself a 1-D array, therefore, B[0] will act as a pointer to the address of  first  element of the array B[0] i.e &B[0][0] which is equal to 400.  

Now the output of
print B+1 = &B[1] which is equal to 412 .

print *(B+1) is same as print B[1] which is equal to a variable name of an array as B[1] is itself a   1-D array, therefore, B[1] will act as a pointer to the address of  first  element of the array B[1] i.e &B[1][0] which is equal to 412.

print *(B+1) + 2 = 420. As *(B+1) is a pointer to an integer containing the address of B[1][0] and if we do pointer arithmetic this will occur in terms of bytes. Therefore B[1] + 2 will give the address of B[1][2].

print *(*B + 1) = 3 . As *B returns a pointer to the first integer of the array B[0] and adding 1 to it will take it to the address of B[0][1] which is equal to the value of &B[0][1] again dereferencing it will give the value stored at B[0][1] which is equal to 3.

For 2-D array,
B[i][j] = *(B[i] + j) = *(*(B+i) + j) 

Now passing  a two-dimensional array into a function:

There are several ways of passing a multidimensional array within a function.

1. one of the ways is to use tempelate :

tempelate<int R,int  C>
void myfunc( int (&array)[R][C])
{
     // do stuff
}

2. Another way of doing this is by using simple arithmetic with passing the address of first block :

void myfunc(int n, int m ,int *arr)    // n rows and m columns 
{
    for(i=0;i<n;i++)
     {
           for(j=0;j<m;j++)
           {
               cout<<*((arr+i*n) + j)        // is same as arr[i][j]
           }
     }
}

int main()
{
     // doing stuffs like declaring an array and initializing it
     //calling the function :->
      myfunc(n,m,(int*)arr);
     

}

Update(8/04/2018):
I was using this approach today for a question where I have to manipulate or say modify the contents of the array by using the above-mentioned method of passing the 2d array. Somehow I ended up with segmentation fault every time. Finally, after debugging my code, I realized that the error was in the indexing i.e instead of using "i" I was using "j". So whats the intention of this post? Actually, while I was facing the segmentation fault, I found another method of passing a 2D array to a function after declaring the array dynamically and this is approach is much simpler.



int edit_distance(int **arr,int n,int m,char *source,char *target)
{
   int i=0,j=0,k;
   
    arr[i][j] = 0; // See you can use the arr[i][j] indexing rather than using the pointer arithmetic
   
   for(j=1;j<=m;j++)
   {
      //cout<<"here"<<endl;
        arr[i][j] = j;
       cout<< arr[i][j];
   }
   j = 0;
   for(i=1;i<=n;i++)
   {
        arr[i][j] = i;
   }
   return 3;

}

int main() {
int t;
cin>>t;
while(t--)
{
    int n,m;
    cin>>n>>m;
    char source[n],target[m];
    cin>>source,target;
    int **arr;
    arr = new int*[n+1];
    for(int i =0;i<=n;i++)
    {
    arr[i] = new int[m+1];
    }
    int ans;
    ans = edit_distance(arr,n,m,source,target);
    
    cout<<ans<<endl;
}
return 0;

}