C++ で書かれており、指定された範囲内の接頭辞と素数の数を見つけます。

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.

#include 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; }

Number of prefix sum prime in given range query: 2