defmodule CountSemiPrimes do
  def count_semi_primes(n, p, q) do
    primes = sieve(n)
    semi_flags = semi_prime_flags(n, primes)
    prefix = prefix_sums(semi_flags, n)

    p
    |> Enum.zip(q)
    |> Enum.map(fn {pi, qi} -> Map.get(prefix, qi) - Map.get(prefix, pi - 1, 0) end)
  end

  defp sieve(n) do
    initial = for i <- 0..n, into: %{}, do: {i, i >= 2}
    limit = :math.sqrt(n) |> trunc()

    Enum.reduce(2..limit//1, initial, fn i, primes ->
      if Map.get(primes, i) do
        Enum.reduce(i * i..n//i, primes, fn k, acc -> Map.put(acc, k, false) end)
      else
        primes
      end
    end)
  end

  defp semi_prime_flags(n, primes) do
    initial = for i <- 0..n, into: %{}, do: {i, 0}
    limit = :math.sqrt(n) |> trunc()

    Enum.reduce(2..limit//1, initial, fn k, flags ->
      if Map.get(primes, k) do
        mark_multiples(k, 2, n, primes, flags)
      else
        flags
      end
    end)
  end

  defp mark_multiples(k, i, n, _primes, flags) when i * k > n, do: flags

  defp mark_multiples(k, i, n, primes, flags) do
    flags = if Map.get(primes, i), do: Map.put(flags, k * i, 1), else: flags
    mark_multiples(k, i + 1, n, primes, flags)
  end

  defp prefix_sums(flags, n) do
    {result, _last} =
      Enum.reduce(1..n//1, {%{0 => Map.get(flags, 0, 0)}, Map.get(flags, 0, 0)}, fn i,
                                                                                      {acc, prev} ->
        cur = prev + Map.get(flags, i, 0)
        {Map.put(acc, i, cur), cur}
      end)

    result
  end
end