11_count_semiprimes.py

"""https://app.codility.com/programmers/lessons/11-sieve_of_eratosthenes/count_semiprimes/"""

from math import floor, sqrt

# Time Complexity:
# Sieve of Eratosthenes to find all primes up to N = O(Nlog(logN))
# For each number up to N, check all possible divisors = O(N*sqrt(N))
# For M queries, return result in O(M)
# Overall: O(Nlog(logN) + Nsqrt(N) + M) = O(Nsqrt(N) + M)

def solution_a(n: int, p: list[int], q: list[int]) -> list[int]:
    """
    P, Q of lengths M represent M queries.
    For each query, find the number of semiprimes within the inclusive range [P[K], Q[K]].
    A semiprime is the product of two prime numbers.
    E.g. 4, 6, 9, 10, 14 .. are semiprimes
    N is the maximum value in P or Q.
    Compute and return the queries

    This solution passes 100% on Codility tests. The detected TC is O(N * log(log(N)) + M),
    which is not the TC we expected: O(Nsqrt(N) + M)
    """

    # sieve[i] is True if i is prime
    sieve = [True] * (n + 1)
    sieve[0] = sieve[1] = False

    # Multiples of the form k * i where k < i are already marked by smaller primes.
    # E.g. for i = 5, multiples 5*2=10, 5*3=15, 5*4=20 are already marked by 2 and 3.
    # Therefore, start from i*i

    i = 2
    while i * i <= n:
        if sieve[i]:
            k = i * i
            while k <= n:
                sieve[k] = False
                k += i
        i += 1

    semiprime_count = 0
    # prefix[i] is the number of semiprimes up to and including number i
    prefix = []
    # For each number check all possible divisors
    for num in range(n+1):
        for divisor in range(2, floor(sqrt(num)) + 1):
            # Definition of semiprime: divisor and quotient are prime
            if sieve[divisor] and num % divisor == 0 and sieve[num // divisor]:
                semiprime_count += 1
        prefix.append(semiprime_count)
    return [prefix[q[i]] - prefix[p[i]-1] for i in range(len(p))]

# Time Complexity:
# Instantiating SPF (smallest prime factor) sieve over [0..N] = O(Nlog(logN))
# Create prefix sum array = O(N)
# Fill prefix sum array with O(1) work per element using SPF = O(N)
# Do M queries, with O(1) work per element using prefix sum array = O(M)
# Overall: O(Nlog(logN) + 2 * N + M) = O(Nlog(logN) + M)

def solution_b(n: int, p: list[int], q: list[int]) -> list[int]:
    """Optimised solution generated by gemini-3-pro (explained in comments)"""

    # spf[i] is the smallest prime factor for number i
    # If spf[i] == 0, then i is prime
    spf = [0] * (n+1)
    i = 2
    while i * i <= n:
        # Sieve if i is prime, recording the smallest prime factor
        if spf[i] == 0:
            k = i * i
            while k <= n:
                if spf[k] == 0:
                    spf[k] = i
                k += i
        i += 1

    # prefix[i] is the number of semiprimes up to and including number i
    prefix = [0] * (n + 1)
    for num in range(2, n + 1):
        # Composite number (candidate for semiprime)
        if spf[num] != 0:
            smallest_prime_factor = spf[num]
            complement = num // smallest_prime_factor
            if spf[complement] == 0:
                prefix[num] += 1
        prefix[num] += prefix[num - 1]

    # Why dividing by SPF can verify semiprimes correctly:
    # 1. If N is prime (single prime factor), we don't enter the conditional (... if spf[num] != 0:)
    # 2. If N is semiprime (2 prime factors), dividing by SPF[N] returns the other prime factor
    # 3. If N has more than 2 prime factors (every other number), dividing by SPF[N]
    #    results in another composite number (not prime)

    return [prefix[q[i]] - prefix[p[i]-1] for i in range(len(p))]