Find Prime Numbers in a Range in C++ (Segmented Sieve Method)

Today, we will see two methods to find the prime numbers in a given range in C++ programming. The problem statement goes like this, we take the lower limit and upper limit for a range. Our task is to check each number from the lower limit to the upper limit to see if any of the numbers are prime and if the number is prime we have to print it on the screen.

For the first method, we will see a direct approach where we go through each number in the range and check if its prime or not. But this is obviously an inefficient method as we have to use two loops. So then we will see a much-refined approach known as the Segmented Sieve method and how it is more efficient than the straight forward solution.

So let’s see both the methods now.

1. Straight forward Method

Look at the C++ code below:

#include<iostream>
using namespace std;
int check_prime(int num)                  // Funcion to check if he number is prime or not
{
 int i;
 for(i=2;i<=num/2;i++)
  if(num%i==0)                           // If a number is divisible by any number then we return 0 since it is composite
   return 0;
 return 1;
}
int main()
{
 int u_rng,l_rng,i;
 cin>>u_rng>>l_rng;                       // Taking upper and lower number for range
 for(i=l_rng;i<=u_rng;i++)
  if(check_prime(i))                      // If the number is prime we print the number
   cout<<i<<" ";
 return 0;
}

As we can see, there are two for-loops here, one for traversing through the numbers in the range and the other to check if the number is divisible by all numbers less than it. So we keep traversing the same numbers again and again and hence this method becomes inefficient. This is a brute force approach to the problem with the time complexity of O(n^2).

Let us see an alternate efficient method:

2. Segmented Sieve Method

To understand the segmented sieve, first, we must know what is the sieve method to find the prime numbers up to a given number. So this simple sieve method involves finding all the primes starting from 2 to a given number.

Let us see how it works:

1.We have an array from 2 to n and mark all of them as prime numbers.

2.We then start from 2 and for each prime number we mark all its multiples to be composite, that is, for 2, we mark 4,6,8, etc. as composite numbers.

3. So if a number is not marked as composite yet, then we mark all its multiples as composite. We do this for all numbers till n.

4. For better optimization, we can start marking the multiples of prime from the square of those numbers to avoid overlapping.

Let us see the code of simple sieve now:

#include<iostream>
#include<vector>
using namespace std;
int main()
{
 int n,i,j;
 vector<int> prime;             // The vector to store if the number is prime or composite
 cin>>n;
 for(i=0;i<=n;i++)              // to initialise all numbers from 2 to n as prime
 {
  if(i==0 || i==1)
   prime.push_back(0);
  else
   prime.push_back(1);
 }
  for(i=0;i<n;i++)              // to check if a position is prime, and if it is then mark al its multiples from its square as composite
  { if(prime[i])
    {
     for(j=i*i;j<=n;j+=i)
      prime[j]=0;
    }
  }
   for(i=0;i<n;i++)             // to display the prime numbers
    if(prime[i])
     cout<<i<<" ";

  return 0;

}

For finding primes in a range we can find all the numbers from 2 to the upper bound of the range and print only the ones in the range. The time complexity of this method is O(n*log log n).

However, this method is not suited for very large numbers as the array size becomes really large. So for large numbers, we go for the method of the segmented sieve.

Here we find the prime numbers from 2 to the square root of the upper range using simple sieve method. Then mark all the multiples of these primes in the given range.

Let us see the C++ code of the segmented sieve method to find the prime numbers in a given range :

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
vector<int> simplesie(int n)              //the previous simple sieve code
{
  int i,j;
  vector<int> prime;
  for(i=0;i<=n;i++)
  {
   if(i==0 || i==1)
    prime.push_back(0);
   else
    prime.push_back(1);
  }
   for(i=0;i<n;i++)
   { if(prime[i])
     {
      for(j=i*i;j<=n;j+=i)
       prime[j]=0;
     }
   }
return prime;

}
int main()
{
  int u,l,r,i,j;
  cin>>l>>u;
  r=sqrt(u);
  vector<int> prime,primer,base;
  prime=simplesie(r);                            // finding the prime numbers upto sqrt(upper bound)
  for(i=l;i<=u;i++)                              // initialising the numbers in the range as prime
  primer.push_back(1);
  for(i=0;i<prime.size();i++)                    // finding the base multiple of each prime for the given range, and assigning -1 if composite
  {if(prime[i])
    base.push_back(l/i);
  else
  base.push_back(-1);
  }
  for(i=0;i<prime.size();i++)                    // for each prime traversing through the range and marking all its multiples as composites
  {
    if(prime[i])
     for(j=i*base[i];j<=u;j+=i)
      primer[j-l]=0;
  }
  for(i=0;i<primer.size();i++)                    // displaying the primes in the range
  if(primer[i])
  cout<<l+i<<" ";
  return 0;

}

This method has the same time complexity as simple sieve. But space complexity wise this is much more efficient when compared to simple sieve. So this the most efficient method to find the prime numbers in a given range.

 

Leave a Reply

Your email address will not be published. Required fields are marked *