資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究使用 C++ 在給定範圍查詢中查詢字首和素數的數量
在本文中，我們需要在一個給定的正整數陣列 arr[ ] 和範圍查詢 **L**、**R** 中找到若干個字首和是素數的個數，其中 **L** 是字首和陣列 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[ ]，並透過將字首和陣列的前一個元素與給定陣列的當前元素相加來填充該陣列。字首和陣列的第一個元素將是給定陣列中索引 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[ ] 並用字首和陣列的前一個元素與給定陣列的當前元素的和來填充它。之後，我們檢查字首陣列的所有數字是否是素數，這裡我們使用埃拉托色尼篩法來檢查素數。最後，為每個素數遞增計數並顯示結果。
結論
在本文中，我們透過應用樸素方法並使用 **埃拉托色尼篩法** 在字首和陣列中查詢素數，解決了在一個給定的範圍查詢中找到若干個字首和是素數的問題。我們可以使用其他語言（如 C、Java、Python 等）編寫相同的程式。希望本文對您有所幫助。
更新於： 2021年11月24日
215 次檢視
廣告