Range Counts with Three Distinct Prime Factors
National Olympiad — National round (2024 season)
Submission name: prime3.cpp
Problem summary
Count integers in each interval [a,b] with exactly three distinct prime divisors, regardless of their multiplicities.
Input
t followed by t pairs a b.
Output
One count per query.
Constraints
0<t<1000; 0<a<b<1000000.
Worked example
Input and output for the worked example discussed below.
Input
3 1 100 140 180 1000 1010
Output
8 9 5
Solution analysis
- Use a sieve counting distinct prime factors. A zero count at p≥2 identifies a prime; increment all its multiples once for this prime.
- Build prefix[x]=prefix[x−1]+[count[x]==3]. Each query answer is prefix[b]−prefix[a−1], so intervals need no repeated factorization.
- In [1,100], the qualifying numbers are 30,42,60,66,70,78,84,90. For example 60=2²×3×5 has three distinct primes, while 16=2⁴ has only one.
Why it works
Every composite has already been visited by a smaller prime, so the sieve identifies all primes correctly. Each prime contributes once to its multiples, giving exact distinct-factor counts. Prefix subtraction then isolates each closed interval.
Complexity: O(U log log U+t) time and O(U) space for U=999999, with O(1) per query.
Watch out. Count distinct primes rather than factors with multiplicity. One has zero primes. Use a−1 for the left endpoint.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
const int limit=999999;
vector<unsigned char>count(limit+1,0);
for(int prime=2;prime<=limit;prime++){
if(count[prime]==0){
for(int multiple=prime;multiple<=limit;multiple+=prime){
count[multiple]++;
}
}
}
vector<int>prefix(limit+1,0);
for(int value=1;value<=limit;value++){
// Prefix subtraction answers each inclusive interval.
prefix[value]=prefix[value-1]+(count[value]==3);
}
int queries;
cin>>queries;
while(queries-->0){
int a;
int b;
cin>>a>>b;
cout<<prefix[b]-prefix[a-1]<<'\n';
}
}