資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用 C++ 查詢子陣列中的素數個數
在本文中，我們將介紹查詢子陣列中素數個數的方法。我們有一個正數陣列 arr[] 和 q 個查詢，每個查詢包含兩個整數，表示我們的範圍 {l, R}，我們需要找到給定範圍內的素數個數。以下是一個給定問題的示例：
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}.查詢解決方案的方法
在這種情況下，我們會想到兩種方法：
暴力法
在這種方法中，我們可以獲取範圍並查詢該範圍內存在的素數個數。
示例
#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'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;
}輸出
2
但是，這種方法不是很好，因為這種方法的整體複雜度為 **O(Q*N*√N)**，這並不是很好。
高效方法
在這種方法中，我們將使用埃拉托色尼篩法建立一個布林陣列，該陣列告訴我們元素是否為素數，然後遍歷給定範圍並在布林陣列中查詢素數的總數。
示例
#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;
}輸出
2
上述程式碼的解釋
這種方法比我們之前應用的暴力法快得多，因為現在的時空複雜度為 **O(Q*N)**，這比之前的複雜度好得多。
在這種方法中，我們預先計算元素並將其標記為素數或非素數；因此，這降低了我們的複雜度。最重要的是，我們還使用了埃拉托色尼篩法，這將幫助我們更快地找到素數。在這種方法中，我們透過使用素因數標記數字，以 **O(N*log(log(N)))** 的複雜度將所有數字標記為素數或非素數。
結論
在本文中，我們解決了一個問題，即使用埃拉托色尼篩法以 O(Q*N) 的時間複雜度查詢子陣列中的素數個數。我們還學習了此問題的 C++ 程式以及解決此問題的完整方法（普通和高效）。我們可以用其他語言（如 C、Java、Python 和其他語言）編寫相同的程式。
更新於：2021 年 11 月 24 日
189 次檢視
廣告