-module(count_semi_primes).
-export([count_semi_primes/3]).

count_semi_primes(N, P, Q) ->
    IsPrime = sieve(N),
    Flags = mark_semiprimes(N, IsPrime),
    Prefix = prefix_cumulative(N, Flags),
    [array:get(Qi, Prefix) - array:get(Pi - 1, Prefix) || {Pi, Qi} <- lists:zip(P, Q)].

sieve(N) ->
    Arr0 = array:new(N + 1, {default, true}),
    Arr1 = array:set(0, false, Arr0),
    Arr2 = case N >= 1 of
        true -> array:set(1, false, Arr1);
        false -> Arr1
    end,
    sieve(2, N, Arr2).

sieve(I, N, Arr) when I * I > N ->
    Arr;
sieve(I, N, Arr) ->
    Arr1 = case array:get(I, Arr) of
        true -> mark_multiples(I * I, I, N, Arr);
        false -> Arr
    end,
    sieve(I + 1, N, Arr1).

mark_multiples(K, _Step, N, Arr) when K > N ->
    Arr;
mark_multiples(K, Step, N, Arr) ->
    mark_multiples(K + Step, Step, N, array:set(K, false, Arr)).

mark_semiprimes(N, IsPrime) ->
    Flags0 = array:new(N + 1, {default, 0}),
    mark_k(2, N, IsPrime, Flags0).

mark_k(K, N, _IsPrime, Flags) when K * K > N ->
    Flags;
mark_k(K, N, IsPrime, Flags) ->
    Flags1 = case array:get(K, IsPrime) of
        true -> mark_i(2, K, N, IsPrime, Flags);
        false -> Flags
    end,
    mark_k(K + 1, N, IsPrime, Flags1).

mark_i(I, K, N, _IsPrime, Flags) when I * K > N ->
    Flags;
mark_i(I, K, N, IsPrime, Flags) ->
    Flags1 = case array:get(I, IsPrime) of
        true -> array:set(K * I, 1, Flags);
        false -> Flags
    end,
    mark_i(I + 1, K, N, IsPrime, Flags1).

prefix_cumulative(N, Flags) ->
    {_, Prefix} = lists:foldl(fun(I, {Prev, Acc}) ->
        Cur = Prev + array:get(I, Flags),
        {Cur, array:set(I, Cur, Acc)}
    end, {0, Flags}, lists:seq(1, N)),
    Prefix.