Prime-Count Queries
Национална олимпиада - Национален кръг 2025
Submission name: primes.cpp
Problem summary
Call an integer P superprime when the number of primes not exceeding P is itself prime. Count such integers in each inclusive query interval. P itself need not be prime.
Input
Q followed by Q pairs L R.
Output
One count per interval.
Constraints
Q ≤ 1000; 2 ≤ L ≤ R ≤ 26000.
Worked example
The worked example illustrates the rule described in the analysis.
Input
2 5 9 4 12
Output
2 5
Solution analysis
- Build a sieve of Eratosthenes. Mark 0 and 1 nonprime, then remove multiples of each prime starting at its square.
- Scan values in increasing order and maintain primeCount = π(value). A value qualifies exactly when prime[primeCount] is true; do not test prime[value] instead.
- Accumulate qualifying values in prefix[value]. An inclusive interval has prefix[R]−prefix[L−1] qualifying integers.
- For 5 through 9, π values are 3,3,4,4,4. Only the first two counts are prime, giving 2.
Why it works
The sieve identifies precisely the primes. The running count therefore equals π(value), so each indicator is correct. Prefix subtraction removes exactly the qualifying integers smaller than L.
Complexity: O(U log log U + Q) time and O(U) space, U=26000; each query is O(1).
Watch out. 1 is not prime. The definition concerns π(P), not whether P is prime. Both endpoints are included.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: The sieve identifies precisely the primes. The running count therefore equals π(value), so
// each indicator is correct.
#include<algorithm>
#include<array>
#include<cstdint>
#include<iostream>
#include<numeric>
#include<string>
#include<vector>
using namespace std;
int main(){
const int limit=26000;
vector<bool>prime(limit+1,true);
prime[0]=prime[1]=false;
for(int p=2;p*p<=limit;++p){
if(prime[p]){
for(int multiple=p*p;multiple<=limit;multiple+=p){
prime[multiple]=false;
}
}
}
vector<int>prefix(limit+1);
int primeCount=0;
for(int value=1;value<=limit;++value){
primeCount+=prime[value];
prefix[value]=prefix[value-1]+prime[primeCount];
}
int queries;
cin>>queries;
while(queries--){
int left,right;
cin>>left>>right;
cout<<prefix[right]-prefix[left-1]<<'\n';
}
}