Problem 187: Semiprimes

Mathematical Analysis

Definition

A semiprime $n$ can be written as $n = p \cdot q$ where $p \le q$ are both prime. The condition $n < 10^8$ means $p \cdot q < 10^8$.

Counting Strategy

For each prime $p$, we count the number of primes $q \ge p$ such that $p \cdot q < 10^8$, i.e., $q < 10^8 / p$.

Since $p \le q$, we need $p^2 < 10^8$, so $p < 10^4 = 10000$. Actually, $p \le \lfloor\sqrt{10^8 - 1}\rfloor = 9999$, so $p$ ranges over all primes up to 9999.

For each such prime $p$, the number of valid primes $q$ is:

where $\pi(x)$ is the prime counting function.

Editorial

Count composite integers n < 10^8 with exactly two prime factors. We use the Sieve of Eratosthenes to find all primes up to $10^8 / 2 = 5 \times 10^7$ (since the smallest prime is 2). We then compute a prefix sum array for the prime counting function. Finally, iterate over each prime $p \le 9999$, add $\pi(\lfloor(10^8 - 1)/p\rfloor) - \pi(p - 1)$ to the answer.

Pseudocode

Use the Sieve of Eratosthenes to find all primes up to $10^8 / 2 = 5 \times 10^7$ (since the smallest prime is 2)
Compute a prefix sum array for the prime counting function
For each prime $p \le 9999$, add $\pi(\lfloor(10^8 - 1)/p\rfloor) - \pi(p - 1)$ to the answer

Proof of Correctness

Every semiprime $n = p \cdot q$ with $p \le q$ is counted exactly once: when we process the smaller prime factor $p$. Since we require $q \ge p$, there is no double-counting.

Correctness

Theorem. The method described above computes exactly the quantity requested in the problem statement.

Proof. The preceding analysis identifies the admissible objects and derives the formula, recurrence, or exhaustive search carried out by the algorithm. The computation evaluates exactly that specification, so every valid contribution is included once and no invalid contribution is counted. Therefore the returned value is the required answer. $\square$

Complexity

• Time: $O(N \log \log N)$ for the sieve where $N = 5 \times 10^7$, plus $O(\sqrt{N})$ for the summation.
• Space: $O(N)$ for the sieve and prefix sums.

Answer

#include <bits/stdc++.h>
using namespace std;

int main() {
    const int LIMIT = 100000000;
    const int SIEVE_SIZE = LIMIT / 2; // max q when p=2

    // Sieve of Eratosthenes
    vector<bool> is_composite(SIEVE_SIZE, false);
    vector<int> primes;

    for (int i = 2; i < SIEVE_SIZE; i++) {
        if (!is_composite[i]) {
            primes.push_back(i);
            if ((long long)i * i < SIEVE_SIZE) {
                for (long long j = (long long)i * i; j < SIEVE_SIZE; j += i) {
                    is_composite[j] = true;
                }
            }
        }
    }

    // For each prime p, count primes q >= p with p*q < LIMIT
    long long count = 0;
    int n = primes.size();

    for (int i = 0; i < n; i++) {
        long long p = primes[i];
        if (p * p >= LIMIT) break;

        // Find largest index j such that primes[j] < LIMIT / p
        // and primes[j] >= p
        long long max_q = (LIMIT - 1) / p;

        // Binary search for max_q in primes
        int lo = i, hi = n - 1, best = i - 1;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (primes[mid] <= max_q) {
                best = mid;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }

        if (best >= i) {
            count += (best - i + 1);
        }
    }

    cout << count << endl;
    return 0;
}

"""
Problem 187: Semiprimes

Count composite integers n < 10^8 with exactly two prime factors.
"""
import bisect

def solve():
    LIMIT = 10**8
    SIEVE_SIZE = LIMIT // 2  # max q when p=2

    # Sieve of Eratosthenes
    is_prime = bytearray(b'\x01') * SIEVE_SIZE
    is_prime[0] = 0
    is_prime[1] = 0

    for i in range(2, int(SIEVE_SIZE**0.5) + 1):
        if is_prime[i]:
            is_prime[i*i::i] = bytearray(len(is_prime[i*i::i]))

    primes = [i for i in range(2, SIEVE_SIZE) if is_prime[i]]

    count = 0
    n = len(primes)

    for i, p in enumerate(primes):
        if p * p >= LIMIT:
            break
        max_q = (LIMIT - 1) // p
        # Find number of primes in [p, max_q]
        j = bisect.bisect_right(primes, max_q) - 1
        if j >= i:
            count += j - i + 1

    print(count)

if __name__ == "__main__":
    solve()