# 計算范圍內的素數 > 原文： [https://www.geeksforgeeks.org/count-primes-ranges/](https://www.geeksforgeeks.org/count-primes-ranges/) 給定范圍[L，R]，我們需要找到范圍為[L，R]的素數總數，其中 0 < = L < = R < 10000。 針對不同范圍的大量查詢。 **示例**： ``` Input : Query 1 : L = 1, R = 10 Query 2 : L = 5, R = 10 Output : 4 2 Explanation Primes in the range L = 1 to R = 10 are {2, 3, 5, 7}. Therefore for query, answer is 4 {2, 3, 5, 7}. For the second query, answer is 2 {5, 7}. ``` 一個**簡單解決方案**是為每個查詢[L，R]執行以下操作。 從 L 遍歷到 R，[檢查當前數字是否為素數](https://www.geeksforgeeks.org/prime-numbers/)。 如果是，則增加計數。 最后返回計數。 一種有效的**解決方案**是使用 Eratosthenes [篩網](https://www.geeksforgeeks.org/sieve-of-eratosthenes/)查找達到給定極限的所有素數。 然后，我們計算一個前綴數組來存儲計數，直到每個值超出限制為止。 一旦有了前綴數組，就可以在`O(1)`時間內回答查詢。 我們只需要返回 prefix [R] – prefix [L-1]。 ## C++ ```cpp // CPP program to answer queries for count of // primes in given range. #include <bits/stdc++.h> using namespace std; const int MAX = 10000; // prefix[i] is going to store count of primes // till i (including i). int prefix[MAX + 1]; void buildPrefix() { ????// Create a boolean array "prime[0..n]". A? ????// value in prime[i] will finally be false? ????// if i is Not a prime, else true. ????bool prime[MAX + 1]; ????memset(prime, true, sizeof(prime)); ????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; ????????} ????} ????// Build prefix array ????prefix[0] = prefix[1] = 0; ????for (int p = 2; p <= MAX; p++) { ????????prefix[p] = prefix[p - 1]; ????????if (prime[p]) ????????????prefix[p]++; ????} } // Returns count of primes in range from L to // R (both inclusive). int query(int L, int R) { ????return prefix[R] - prefix[L - 1]; } // Driver code int main() { ????buildPrefix(); ????int L = 5, R = 10; ????cout << query(L, R) << endl; ????L = 1, R = 10; ????cout << query(L, R) << endl; ????return 0; } ```