Written in C++, find the number of prefix and prime numbers in a given range-C++-php.cn

Written in C++, find the number of prefix and prime numbers in a given range

WBOY

Release： 2023-08-25 14:37:11

forward

776 people have browsed it

Written in C++, find the number of prefix and prime numbers in a given range

In this article, we need to find multiple prime prefix sums in the given positive integer array arr[] and perform range queriesL,R, where L is the initial index value arr[ L ] of the prefixsum[ ] array, R is the number of prefix sums we need to find.

To fill the prefix sum array, we start from index L to index R and add the current value with the last element in the given array. Here is the example of the problem -

Input : arr[ ] = { 3, 5, 6, 2, 4 }
L = 1, R = 3
Output : 3
Explanation : prefixsum[ 0 ] = arr[ L ] = 5
prefixsum[ 1 ] = prefixsum[ 0 ] + arr[ 2 ] = 11
prefixsum[ 2 ] = prefixsum[ 1 ] + arr[ 3 ] = 13
In prefixsum[ ] array all three 5, 11 and 13 are prime numbers in prefix sum array in given range.

Input : arr[ ] = { 6, 10, 5, 8, 11 }
L = 0, R = 3
Output : 1
Explanation : prefixsum[ 0 ] = arr[ L ] = 6
prefixsum[ 1 ] = prefixsum[ 0 ] + arr[ 1 ] = 16
prefixsum[ 2 ] = prefixsum[ 1 ] + arr[ 2 ] = 21
prefixsum[ 3 ] = prefixsum[ 2 ] + arr[ 3 ] = 29
In prefixsum[ ] array only 29 is the prime number in prefix sum array given range.

Copy after login

Ways to find the solution

From this question we can say we need to create a new array prefixsum[ ] and add prefix sum to the front of the array An element and the current element of the given array. The first element of the prefix sum array will be the value at index L in the given array.

We need to run a loop from L to R, where L and R are the given arrays, and then check the elements of the prefixsum[ ] array and increment the count for each prime found.

Example

#include<bits/stdc++.h>
using namespace std;
vector < bool > checkprime (int *arr, int n, int MAX){
    vector < bool > p (n);
    bool Prime_val[MAX + 1];
    for (int i = 2; i < MAX; i++)
        Prime_val[i] = true;
        Prime_val[1] = false;
    for (int p = 2; p * p <= MAX; p++){
        // If prime[p] is not changed, then
        // it is a prime
        if (Prime_val[p] == true){
            // Update all multiples of p
            for (int i = p * 2; i <= MAX; i += p)
                Prime_val[i] = false;
        }
    }
    for (int i = 0; i < n; i++){
        if (Prime_val[arr[i]])
             p[i] = true;
        else
        p[i] = false;
    }
    return p;
}
int main (){
    int arr[] = { 2, 3, 4, 7, 9, 10 };
    int s1 = sizeof (arr) / sizeof (arr[0]);//size of given array
    int L = 1, R = 3, s2 = R - L + 1;
    int prefixsum[s2];
    int count = 0;
    prefixsum[0] = arr[L];
    for (int i = L + 1, j = 1; i <= R && j < s1; i++, j++){
        prefixsum[j] = prefixsum[j - 1] + arr[i];

    }
    vector < bool > isprime = checkprime (prefixsum, s2, prefixsum[s2 - 1]);
    for (int i = 0; i < s2; i++) {
        if (isprime[i] == 1)
            count++;
    }
    cout <<"Number of prefix sum prime in given range query: " << count;
    return 0;
}

Copy after login

Output

Number of prefix sum prime in given range query: 2

Copy after login

Explanation of the above code

In this code, we create an array prefixsum[ ] and use prefixsum[ ] of the array Fills it with the sum of the previous element and the current element of the given array. After that we check if all the numbers of the prefix array are prime or not, here we are using Sieve of Eratosthenes algorithm to check for prime numbers. Finally, increase the count for each prime and display the result.

Conclusion

In this article, we found prime numbers in prefix sum arrays by applying a naive approach and using Sieve of Eratosthenes. We can write the same program in other languages such as C, java, python and other languages. Hope this article is helpful to you.

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