Count Primes in Ranges

Difficulty Level Medium
Frequently asked in Google Hike Kuliza Sieve Snapchat Yahoo
Math Number SystemViews 1493

Problem Statement

The problem “Count Primes in Ranges” states that you are given a range [left, right], where 0<=left<=right<=10000. The problem statement asks to find out the total number of prime numbers within the range. Assuming that there will be a large number of queries.

Example

left: 4
right:10
2

Explanation

5 and 7 are the only 2 prime numbers.

Count Primes in Ranges

left: 6
right:8
1

Explanation

7 is the only prime number.

Algorithm

  1. Create an integer array and Boolean array ‘prime’ of maximum given size and initialize the Boolean array with true.
  2. Traverse the Boolean array and check if the current value of the ‘prime’ array is true.
  3. Then start traversing from the current array element and initialize each array element from then on to false which is at a distance equal to the magnitude of the current element. This means we are moving to the multiples of the current element.
  4. Set prePrime[0] and prePrime[1] to 0.
  5. Traverse from the 2 till the maximum given value.
  6. Copy the value to the previous index of prePrime array and check if the prime array’s current value is equal to true, then increase the value of prePrime’s value by 1.
  7. For each query return the difference of prePrime[right] and prePrime[left-1].

Explanation

Given a range of a number as a starting number and an ending number. Thus considering this range as it is filled with all of the in-between numbers. We have asked to find out the total number of prime numbers within this range. For this, we will be building a prePrime array through which we can solve any query within the range of maximum number. Declare an integer array of max size of 10000 which is given to us, and with the same size, we will declare a Boolean array of which we initialized as a value true.

Traverse in a loop from the value two because we cannot consider one as a prime number. Check each number of Boolean prime array’s each value is equal to true, if it is found to be true, then we will move further to traverse in a loop. We will start from the twice of the current number and move forward to its multiples till the value of max size is reached and initialize each value from then on to false. This approach is generally referred to as Sieve of Eratosthenes.

We set the value of 0th and 1st value of prePrime array to 0. So that we will start from 2 to traverse the prePrime and prime array. Then we copy the next value of prePrime array to the previous value of prePrime array and check if the prime array’s current value is true, if true then increase the value of prePrime array’s current element. For each query we will receive as a starting number and an ending number. We will return the difference of prePrime[right] and prePrime[left-1]. That will be the required answer.

Code

Implementation in C++ to count primes in ranges

#include<iostream>
#include<stdio.h>
#include<cstring>

using namespace std;

const int MAX = 10000;

int prePrime[MAX + 1];

void PrePrimeFunction ()
{

    bool prime[MAX + 1];
    memset(prime, true, sizeof(prime));

    for (int a = 2; a * a <= MAX; a ++)
    {
        if (prime[a] == true)
        {
            for (int i = a * 2; i <= MAX; i += a)
                prime[i] = false;
        }
    }
    prePrime[0] = prePrime[1] = 0;
    for (int q = 2; q <= MAX; q++)
    {
        prePrime[q] = prePrime[q - 1];
        if (prime[q])
            prePrime[q]++;
    }
}

int solveQuery(int L, int R)
{
    return prePrime[R] - ((L>0) ? prePrime[L - 1] : 0);
}

int main()
{
    PrePrimeFunction();

    int L = 4, R = 10;
    cout << solveQuery(L, R) << endl;

    L = 6, R = 8;
    cout << solveQuery(L, R) << endl;

    return 0;
}

2
1

Implementation in Java to count primes in ranges

import java.util.Arrays;

class PrimeInRange
{

    static final int MAX = 10000;

    static int prePrime[] = new int[MAX + 1];

    static void PrePrimeFunction()
    {

        boolean prime[] = new boolean[MAX + 1];
        Arrays.fill(prime, true);

        for (int a = 2; a * a <= MAX; a++)
        {
            if (prime[a] == true)
            {

                for (int i = a * 2; i <= MAX; i += a)
                    prime[i] = false;
            }
        }

        prePrime[0] = prePrime[1] = 0;

        for (int q = 2; q <= MAX; q++)
        {
            prePrime[q] = prePrime[q - 1];
            if (prime[q])
                prePrime[q]++;
        }
    }

    static int solveQuery(int L, int R)
    {
        return prePrime[R] - ((L>0) ? prePrime[L - 1] : 0);
    }

    public static void main(String[] args)
    {
        PrePrimeFunction();
        int L = 4, R = 10;
        System.out.println(solveQuery(L, R));

        L = 6;
        R = 8;
        System.out.println(solveQuery(L, R));
    }
}

2
1

Complexity Analysis

Time Complexity

O(n*log(log(n)) + q) where “n” is the number of elements in the array and “q” is the number of queries. Thus this time complexity is because of the algorithm we have used “Sieve of Eratosthenes”.

Space Complexity

O(1) because the size of the array is not dependent on the input, it is equal to a constant value. Because space is required to store the result of the primes. Since we store if the number is prime or not.

Translate »