import Control.Monad (forM_, when)
import Control.Monad.ST (runST)
import Data.Array (Array, listArray, (!))
import Data.Array.ST (newArray, readArray, runSTUArray, writeArray)
import Data.Array.Unboxed (UArray)

isPrimeArr :: Int -> UArray Int Bool
isPrimeArr n = runSTUArray $ do
  arr <- newArray (0, n) True
  forM_ [2 .. floor (sqrt (fromIntegral n :: Double))] $ \i -> do
    p <- readArray arr i
    when p $ forM_ [i * i, i * i + i .. n] $ \k -> writeArray arr k False
  return arr

semiPrimeArr :: Int -> UArray Int Bool -> UArray Int Bool
semiPrimeArr n primes = runSTUArray $ do
  arr <- newArray (0, n) False
  forM_ [k | k <- [2 .. floor (sqrt (fromIntegral n :: Double))], primes ! k] $ \k ->
    forM_ (takeWhile (\i -> i * k <= n) [2 ..]) $ \i ->
      when (primes ! i) $ writeArray arr (k * i) True
  return arr

prefixCounts :: Int -> UArray Int Bool -> Array Int Int
prefixCounts n semi =
  listArray (0, n) (scanl1 (+) (0 : [if semi ! i then 1 else 0 | i <- [1 .. n]]))

countSemiPrimes :: Int -> [Int] -> [Int] -> [Int]
countSemiPrimes n p q = [prefix ! qi - prefix ! (pi' - 1) | (pi', qi) <- zip p q]
  where
    primes = isPrimeArr n
    semi   = semiPrimeArr n primes
    prefix = prefixCounts n semi