gaff

{-# LANGUAGE ScopedTypeVariables #-}

-- | this code solves (fast) the primacity problem in facebook hackathon 2015.
--
--   basically, given 3 positive integers -- A, B, K -- output number of items
--   in [A, B] with primacity K.  For example, if A=5, B=15, K=2, the program
--   will output 5 -- i.e., 5 numbers in [5, 15] have primacity 2.
--
--   NOTE: we must always have 2 <= A <= B, K >= 1.
--
--   for details, see ~/software-development/notes/facebook-hackathon-2015.pages
--
--   author & source: /u/ Siddhanathan @ https://goo.gl/Yv4XMh (stackoverflow).

-- NOTE:
--  with base-4.8, Prelude re-exports a few more entities from modules such as
--  Data.Monoid and Control.Applicative, which makes below 2 imports in the
--  original code redundant.
--  REF: see https://gitlab.haskell.org/ghc/ghc/-/wikis/migration/7.10
--  import Control.Applicative ( pure, (<$>) )
--  import Data.Monoid         ( (<>) )

module Primacity where

import Data.List           ( nub )

isPrime :: forall i. Integral i => i -> Bool
isPrime n = isPrime_ n primes
  where isPrime_ :: i -> [i] -> Bool
        isPrime_ m [] = isPrime_ m primes   -- this case should never happen
        isPrime_ m (p:ps)
            | p * p > m      = True
            | m `mod` p == 0 = False
            | otherwise      = isPrime_ m ps

primes :: (Integral i) => [i]
primes = 2 : filter isPrime [3,5..]

primeFactors :: forall i. Integral i => i -> [i]
primeFactors n = factors n primes
  where factors :: i -> [i] -> [i]
        factors m [] = factors m primes     -- this case should never happen
        factors m (x:xs)
            | x * x > m      = [m]
            | m `mod` x == 0 = x : factors (m `div` x) (x:xs)
            | otherwise      = factors m xs

primacity :: (Integral i) => i -> Int
primacity = length . nub . primeFactors

primacityCount :: (Integral i) => [i] -> Int -> Int
primacityCount x k = length . filter (== k) . fmap primacity $ x

df :: IO ()
df = do
  let a :: Int = 2
      b :: Int = 10000000
      k :: Int = 1
      n = primacityCount [a..b] k
  putStrLn $ show n


{-# LANGUAGE ScopedTypeVariables #-}

module Main (main) where

import Primacity

dff :: IO ()
dff = do
  let a :: Int = 2
      b :: Int = 10000000
      k :: Int = 1
      n = primacityCount [a..b] k
  putStrLn $ show n

-- using GHC 8.10.4
-- ghc options used:
  --  '-O2 -fforce-recomp -Wall -Werror'
  --  '-fforce-recomp -Wall -Werror'
main :: IO ()
main = do
  df    -- this call works just fine.
  -- but below call to `dff`, which is identical to `df` in `Primacity.hs`,
  -- hangs.  however, if input `b` in `dff` is small, say 100, it works.
  dff