使用C++編寫，找到給定範圍內前綴和質數的數量

在本文中，我們需要在給定的正整數陣列arr[ ] 中尋找多個質數前綴和，並進行範圍查詢L、R ，其中L 是prefixsum[ ] 陣列的初始索引值arr[ L ]，R 是我們需要尋找的前綴和的數量。

為了填滿前綴和數組，我們從索引 L 開始到索引 R，並將當前值與給定數組中的最後一個元素相加。這是問題的範例-

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.

尋找解決方案的方法

從這個問題來看，我們可以說我們需要建立一個新陣列prefixsum[ ] 並且透過新增prefix sum 陣列的前一個元素和給定數組的當前元素。前綴和數組的第一個元素將是給定數組中索引 L 處的值。

我們需要執行一個從 L 到 R 的循環，其中 L 和 R 是要在給定數組，然後檢查 prefixsum[ ] 數組的元素並增加找到的每個素數的計數。

範例

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

輸出

Number of prefix sum prime in given range query: 2

上述程式碼的解釋

在此程式碼中，我們建立一個陣列prefixsum[ ] 並用prefixsum[ ] 陣列的前一個元素與給定數組的當前元素總和填充它。之後，我們檢查前綴數組的所有數字是否有素數，這裡我們使用埃拉托色尼篩法演算法來檢查素數。最後，增加每個質數的計數並顯示結果。

結論

在本文中，我們透過應用天真的方法並使用埃拉托斯特尼篩選法在前綴和陣列中尋找素數。我們可以用其他語言像是C、java、python等語言來寫同樣的程式。希望這篇文章對您有幫助。

以上是使用C++編寫，找到給定範圍內前綴和質數的數量的詳細內容。更多資訊請關注PHP中文網其他相關文章！