Count Prime in Ranges

Sample Example

Let's take a simple example to understand the problem better.

Input:

Q = 1

L = 2

R = 9

Output:

4

Explanation : 

There are 4 prime numbers in the range [2 , 9] inclusive which are 2, 3, 5, 7.

Brute Force Approach

This is the simple approach where we loop between L to R to calculate the number of primes in that range.

Algorithm

1. Loop through each query and for each query, loop through all numbers from L to R inclusive.
2. For each number, check if it is a prime number by dividing it by all numbers from 2 to sqrt(itself).
3. If it is a prime number, increment a count variable.
4. Print the count variable as the answer for the current query.

Dry Run 

Let's assume queries to be 1 and L = 2 & R = 9

We start by initialising Q to 1 and reading the values of queryL and queryR as 2 and 9, respectively. We then enter a loop that iterates from j = queryL = 2 to j <= queryR = 9.

For each value of j, we check if it is prime by calling the isPrime() function. In this case, when j = 2, the function returns true because 2 is a prime number. When j = 3, the function also returns true because 3 is a prime number. When j = 4, the function returns false because 4 is not a prime number. This pattern continues for the rest of the loop iterations until j = 9.

Finally, we output the value of count, which is the number of prime numbers between queryL and queryR.

So for Q = 1, L = 2 , and R = 9, the program outputs 4, which represents the number of prime numbers between 2 and 9 (namely, 2, 3, 5, and 7).

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

bool isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    int L = 2 , R = 9;
    int count = 0;
    for (int j = L; j <= R; j++) {
        if (isPrime(j)) count++;
    }
    cout << "Count of prime numbers between " << L << " and " << R << " inclusive: " << count<< endl;
    return 0;
}

Output

Implementation in Java

import java.util.Scanner;

public class PrimeCount {
    public static boolean isPrime(int n) {
        if (n <= 1) return false;
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int L = 2 , R = 9;
        int count = 0;
        for (int j = L; j <= R; j++) {
            if (isPrime(j)) count++;
        }
        System.out.println("Count of prime numbers between " + L + " and " + R + " inclusive: " + count);
        scanner.close();
    }
}

Output

Time Complexity

The time complexity of the given code is O( Q * ( R - L) * sqrt(R)) where Q is the number of queries, L and R are the range of each query. The inner loop iterates from L to R, and for each number, it calls the isPrime function which has a time complexity of O(sqrt(R)). Therefore, the overall time complexity of the code is O( Q * (R - L) * sqrt(R)).

Space Complexity

The space complexity of the given code is O(1) since it only uses a fixed amount of memory for the input variables, a few loop counters, and a single boolean variable.

Optimised Approach

To optimise the brute force approach, we can make use of the Sieve of Eratosthenes algorithm to generate all prime numbers up to the largest value of R. Then for each query, we can use these precomputed primes to count the number of primes between L and R.

Algorithm

1. Firstly we build sieve-of-eratosthenes.
2. Create a prefix sum array prefixCount of size N and initialise prefixCount[0] and prefixCount[1] as 0 , N being the largest value we can have for R which in this case is 1e6.
3. Iterate through all numbers from 2 to n-1 and set prefixCount[i] to prefixCount[i-1] if isPrime[i] is false, and to prefixCount[i-1]+1 if isPrime[i] is true.
4. For each query of the form (L,R), output prefixCount[R]-prefixCount[L-1] for L>0 and for L=0 , we output prefixCount[R] ,  which gives the count of prime numbers between L and R inclusive.

Dry Run 

Let's assume queries to be 1 and L = 2 & R = 9

1. The program starts by asking for the number of queries, which is 1 in this case.
2. It initializes two vectors, isPrime and prefixCount, each of size N+1 ,  N being the largest value we can have for R which can go upto 100000.
3. It then calls the generatePrimes() function to generate all prime numbers up to the limit N using the Sieve of Eratosthenes algorithm.
4. After that, it calls the calculatePrefixCount() function to calculate the prefix count of prime numbers up to each number using the isPrime vector.
5. Now, the program enters the loop to handle the single query that we have. It asks for L and R, which are 2 and 9 respectively in this case.
6. It then checks if the input is valid and within the limit. Since it is valid, it calls the countPrimes() function to find the count of prime numbers between 2 and 9 (inclusive) using the prefix count approach.
7. The count is calculated as prefixCount[R] - prefixCount[L-1], which is 4 - 0 = 4 in this case.
8. Finally, the program outputs the count of prime numbers between 2 and 9 (inclusive), which is 4.

Implementation in C++

#include <iostream>
#include <vector>
using namespace std;

const int N = 1000000 + 1; // Maximum value of R+1

vector<bool> isPrime(N + 1, true);
vector<int> prefixCount(N + 1, 0);

// Function to generate all primes using Sieve of Eratosthenes
void generatePrimes()
{
    isPrime[0] = isPrime[1] = false;


    for (int i = 2; i * i <= N; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= N; j += i) {
                isPrime[j] = false;
            }
        }
    }
}

// Function to calculate prefix count of primes
void calculatePrefixCount()
{
    for (int i = 1; i <= N; i++) {
        prefixCount[i] = prefixCount[i - 1];
        if (isPrime[i]) {
            prefixCount[i]++;
        }
    }
}

// Function to count primes between L and R inclusive
int countPrimes(int L, int R)
{
   if(L==0) return prefixCount[R];
   else return prefixCount[R] - prefixCount[L - 1];
}

int main()
{
    int L = 2, R = 9;
    generatePrimes();
    calculatePrefixCount();
    
    cout << "Count of prime numbers between " << L << " and " << R << " inclusive: " << countPrimes(L, R) << endl;

    return 0;
}

Output

Implementation in Java

import java.util.*;

public class Main {
    static final int N = 1000000 + 1; // Maximum value of R

    static boolean[] isPrime = new boolean[N + 1];
    static int[] prefixCount = new int[N + 1];

// Function to generate all primes using Sieve of Eratosthenes
    static void generatePrimes() {
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;


        for (int i = 2; i * i <= N; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= N; j += i) {
                    isPrime[j] = false;
                }
            }
        }
    }

// Function to calculate prefix count of primes
    static void calculatePrefixCount() {
        for (int i = 1; i <= N; i++) {
            prefixCount[i] = prefixCount[i - 1];
            if (isPrime[i]) {
                prefixCount[i]++;
            }
        }
    }

// Function to count primes between L and R inclusive
    static int countPrimes(int L, int R) {
        if(L == 0) return  prefixCount[R];
        else return  prefixCount[R] - prefixCount[L - 1];
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int L =2 , R = 9;

        generatePrimes();
        calculatePrefixCount();

        System.out.println("Count of prime numbers between " + L + " and " + R + " inclusive: " + countPrimes(L, R));
        scanner.close();
    }
}

Output

Time Complexity

The time complexity of the code is O(R log(log(R)) + Q) due to the Sieve of Eratosthenes algorithm and the prefix sum computation. Here, R is the upper limit of the range of numbers and Q is the number of queries. 

Space Complexity

The space complexity is O(R) due to the storage of the boolean array isPrime and the prefix sum array prefixCount.

Frequently Asked Questions

What is a prime number?

A prime number is a positive integer greater than 1 that has no positive integer divisors other than 1 and itself.

What is the most basic algorithm for determining if a number is prime?

The most basic algorithm for determining if a number is prime is to check if it is divisible by any integer between 2 and its square root. If it is not divisible by any of these integers, it is prime.

What is the Sieve of Eratosthenes?

The Sieve of Eratosthenes is an algorithm for generating all prime numbers up to a given limit. It works by iteratively marking the multiples of each prime, starting with 2, and then proceeding to the next unmarked number. The algorithm terminates when the square of the next prime exceeds the given limit.

What is the time complexity of the basic algorithm for determining if a number is prime?

The time complexity of the basic algorithm for determining if a number is prime is O(sqrt(n)), where n is the number being tested.

What is the time complexity of the Sieve of Eratosthenes algorithm?

The time complexity of the Sieve of Eratosthenes algorithm is O(n log log n), where n is the limit up to which prime numbers are generated.

Conclusion

In this discussion, we talked about the problem of counting prime numbers between a given range. We discussed two different approaches, one brute-force solution with a time complexity of O(N * sqrt(N)), and another optimized solution using the Sieve of Eratosthenes algorithm with a time complexity of O(N * log(log(N)) + Q), where Q is the number of queries. 
 

We hope this blog has helped you in counting primes in a range. You can check the following blogs to read more about related topics.

• Sieve of Eratosthenes with Linear time complexity
• Prime Numbers
• Segmented Sieve

And many more on our platform Coding Ninjas Studio.

Refer to our Guided Path to upskill yourself in DSA, Competitive Programming, JavaScript, System Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio!
 

But suppose you have just started your learning process and are looking for questions from tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problems, interview experiences, and interview bundles for placement preparations.
 

However, you may consider our paid courses to give your career an edge over others!

Happy Learning, Ninjas!