Written in C++, find the number of prime numbers in a subarray

In this article, we will describe the method of finding the number of prime numbers in a subarray. We have an array arr[] of positive numbers and q queries with two integers representing our range {l, R} and we need to find the number of prime numbers in the given range. Below is an example of the given problem -

Input : arr[] = {1, 2, 3, 4, 5, 6}, q = 1, L = 0, R = 3

Output : 2

In the given range the primes are {2, 3}.

Input : arr[] = {2, 3, 5, 8 ,12, 11}, q = 1, L = 0, R = 5

Output : 4

In the given range the primes are {2, 3, 5, 11}.

Methods to find the solution

In this case, I thought of two methods-

Brute force cracking

In this method we can take a range and find out the number of prime numbers present in that range.

Example

#include <bits/stdc++.h>
using namespace std;
bool isPrime(int N){
    if (N <= 1)
       return false;
    if (N <= 3)
       return true;
    if(N % 2 == 0 || N % 3 == 0)
       return false;
    for (int i = 5; i * i <= N; i = i + 2){ // as even number can&#39;t be prime so we increment i by 2.
       if (N % i == 0)
           return false; // if N is divisible by any number then it is not prime.
    }
    return true;
}
int main(){
    int N = 6; // size of array.
    int arr[N] = {1, 2, 3, 4, 5, 6};
    int Q = 1;
    while(Q--){
        int L = 0, R = 3;
        int cnt = 0;
        for(int i = L; i <= R; i++){
           if(isPrime(arr[i]))
               cnt++; // counter variable.
        }
        cout << cnt << "\n";
    }
    return 0;
}

Output

2

However, this method is not very good because the overall complexity of this method is O(Q*N* √N), that’s not very good.

Efficient method

In this method we will use the Sieve of Eratosthenes to create a boolean array that tells us whether the element is prime or not and then iterate over the given range and find the total number of prime numbers in this array. boolean array.

Example

#include <bits/stdc++.h>
using namespace std;
vector<bool> sieveOfEratosthenes(int *arr, int n, int MAX){
    vector<bool> p(n);
    bool Prime[MAX + 1];
    for(int i = 2; i < MAX; i++)
       Prime[i] = true;
    Prime[1] = false;
    for (int p = 2; p * p <= MAX; p++) {
       // If prime[p] is not changed, then
       // it is a prime
       if (Prime[p] == true) {
           // Update all multiples of p
           for (int i = p * 2; i <= MAX; i += p)
               Prime[i] = false;
       }
    }
    for(int i = 0; i < n; i++){
        if(Prime[arr[i]])
           p[i] = true;
        else
           p[i] = false;
    }
    return p;
}
int main(){
    int n = 6;
    int arr[n] = {1, 2, 3, 4, 5, 6};
    int MAX = -1;
    for(int i = 0; i < n; i++){
        MAX = max(MAX, arr[i]);
    }
    vector<bool> isprime = sieveOfEratosthenes(arr, n, MAX); // boolean array.
    int q = 1;
    while(q--){
        int L = 0, R = 3;
        int cnt = 0; // count
        for(int i = L; i <= R; i++){
            if(isprime[i])
               cnt++;
       }
       cout << cnt << "\n";
   }
   return 0;
}

Output

2

Explanation of the above code

This method is much faster than the brute force method we applied before, because now The time complexity is O(Q*N), i.e. much better than the previous complexity.

In this approach, we precompute the elements and mark them as prime or non-prime; therefore, this reduces our complexity. In addition to this, we are also using the Sieve of Eratosthenes, which will help us find prime numbers faster. In this method, we label all numbers as prime or non-prime with O(N*log(log(N))) complexity by labeling the numbers with prime factors.

Conclusion

In this article, we solved the problem of finding the number of prime numbers in a subarray in O(Q*N) using the Sieve of Eratosthenes. We also learned a C program to solve this problem and a complete way to solve this problem (normal and efficient). We can write the same program in other languages, such as C, java, python and other languages.

The above is the detailed content of Written in C++, find the number of prime numbers in a subarray. For more information, please follow other related articles on the PHP Chinese website!