Classify Products of Primes
National Olympiad — Regional round (2025 season)
Submission name: product.cpp
Problem summary
For every integer in the inclusive interval [A,B], count four properties: divisible by 2 or 3; prime; a product of exactly two distinct primes; and a product of exactly three or four primes with repetitions allowed.
Input
A B.
Output
Four lines containing the four counts in the stated order.
Constraints
2 ≤ A ≤ B < 5000000; B−A ≤ 500.
Worked example
An independently prepared example for this explanation.
Input
2 10
Output
7 4 2 1
Solution analysis
- The interval is narrow, so factor each value independently by trial division. Repeatedly divide by each candidate factor and record both the total number of prime factors with multiplicity and the number of distinct factors.
- A number is prime when the total factor count is one. A product of two distinct primes has total count two and distinct count two. The last category requires total count three or four; it does not require distinctness.
- For 2…10, the primes are 2,3,5,7. Products of two different primes are 6 and 10. Only 8=2·2·2 has three or four prime factors. Divisibility by 2 or 3 is tested once with a logical OR, producing seven.
Why it works
Trial division removes each smallest remaining factor completely; every removed factor is prime, and a final remaining value above one is prime. Thus the multiplicity and distinct counts are exact, and the four predicates match the requested definitions.
Watch out. Prime squares such as 4 and 9 do not qualify for the third count. For the fourth count, repeated primes do count separately. A multiple of both 2 and 3 counts only once in the first line.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
using namespace std;
int main() {
int a, b;
cin >> a >> b;
int divisible = 0, prime = 0, twoDistinct = 0, threeOrFour = 0;
for (int number = a; number <= b; number++) {
if (number % 2 == 0 || number % 3 == 0) {
divisible++;
}
int remaining = number;
int totalFactors = 0, distinctFactors = 0;
for (int factor = 2; factor <= remaining / factor; factor++) {
if (remaining % factor == 0) {
distinctFactors++;
// Count prime factors with multiplicity, not just distinct factors.
while (remaining % factor == 0) {
totalFactors++;
remaining /= factor;
}
}
}
if (remaining > 1) {
totalFactors++;
distinctFactors++;
}
if (totalFactors == 1) {
prime++;
}
if (totalFactors == 2 && distinctFactors == 2) {
twoDistinct++;
}
if (totalFactors == 3 || totalFactors == 4) {
threeOrFour++;
}
}
cout << divisible << '\n' << prime << '\n' << twoDistinct << '\n' << threeOrFour << '\n';
}