A specialized variant of the Sieve of Eratosthenes can simultaneously tag integer primality and record the count of prime factors for each composite. This technique is particularly effective when searching for numbers within a range whose total number of prime factors (with multiplicity) equals a given constant.

Two data structures are central: prime_marker acts as both a primality flag and a factor counter, initialized to 0 for all entries, while primes stores every discovered prime in sequence.

Step 1 – Identification and Initialization

Iterate candidate from 2 up to the defined maximum limit R. When prime_marker[candidate] equals 0, the number is a prime. Set prime_marker[candidate] = 1 to indicate it consists of exactly one prime factor, and append candidate to the primes list.

if (prime_marker[candidate] == 0) {
    prime_marker[candidate] = 1;
    primes.push_back(candidate);
}

Step 2 – Range Check and Aggregation

If candidate lies inside the target interval [L, R], verify whether prime_marker[candidate] equals the required count, here 12. Increment a counter if the condition holds.

if (candidate >= L && prime_marker[candidate] == 12) {
    result++;
}

Step 3 – Marking Multiples with Accumulated Factor Counts

For each previously discovered prime p, compute the product multiple = p * candidate. If multiple exceeds R, terminate the inner loop early. Otherwise, assign prime_marker[multiple] = prime_marker[candidate] + 1. This addition reflects the fact that multiple inherits every prime factor of candidate plus the extra prime p itself.

for (int p : primes) {
    long long mult = 1LL * p * candidate;
    if (mult > R) break;
    prime_marker[mult] = prime_marker[candidate] + 1;
}

The algorithm works because composite numbers are generated in increasing order by multiplying smaller candidates with primes already seen. At the moment a composite is first formed, the factor count of its source is known, so the new count becomes source_count + 1. The initial zero value acts as an indicator that a number has not yet been encountered and is therefore prime.

Full C++ implementation:

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    const long long L = 2333333, R = 23333333;
    vector<int> prime_marker(R + 5, 0);
    vector<int> primes;
    int answer = 0;

    for (int num = 2; num <= R; ++num) {
        if (prime_marker[num] == 0) {
            prime_marker[num] = 1;
            primes.push_back(num);
        }

        if (num >= L && prime_marker[num] == 12) {
            answer++;
        }

        for (int p : primes) {
            long long val = 1LL * p * num;
            if (val > R) break;
            prime_marker[val] = prime_marker[num] + 1;
        }
    }

    cout << answer << endl;
    return 0;
}

This method avoids separate factorization runs while efficiently scanning the target range, making it suitable for large upper bounds where checking each number individually would be too slow.