Many Prime-Count Interval Queries
National Olympiad — National round (2013 season)
Submission name: primecnt.cpp
Problem summary
Count primes in each of k inclusive integer intervals.
Input
k followed by k pairs a b.
Output
One prime count per query line.
Constraints
1 ≤ a ≤ b ≤ 10^6; 1 ≤ k ≤ 1000.
Worked example
Input and output for the worked example discussed below.
Input
3 2 20 20 100 1 100
Output
8 17 25
Solution analysis
- Classify integers through one million with Eratosthenes’ sieve. Mark 0 and 1 nonprime, then mark multiples starting at p² for each remaining prime p.
- Build prefix[x], the count of primes from 1 through x. A query [a,b] is prefix[b]−prefix[a−1], so all expensive classification work is shared.
- The eight primes in [2,20] are 2,3,5,7,11,13,17,19. There are 17 in [20,100] and 25 in [1,100], matching the three sample lines.
Why it works
The sieve correctly marks every composite through a prime factor. Prefix subtraction removes exactly primes below a and retains those through b, giving the inclusive interval count.
Complexity: O(U log log U) preprocessing time and O(U) space for U=10^6. Each query is O(1), so total time is O(U log log U+k).
Watch out. One is not prime. Subtract the prefix at a−1 to include a. Equal endpoints are allowed.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
using namespace std;
int main(){
const int limit=1000000;
vector<bool>prime(limit+1,true);
prime[0]=false;
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);
for(int value=1;value<=limit;value++){
prefix[value]=prefix[value-1]+prime[value];
}
int queries;
cin>>queries;
while(queries--){
int left;
int right;
cin>>left>>right;
// Exclude only primes strictly before the interval.
cout<<prefix[right]-prefix[left-1]<<'\n';
}
}