eratosthenes-bad.hs

{-# OPTIONS_GHC -fno-warn-type-defaults #-}

module Main where

import           Data.List ((\\))
import qualified Data.Vector as V


main :: IO ()
main = print $ sum $ primeSieveAlsoBad 50000

-- | https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
--
-- This has a couple of "improvements":
-- 1. Only cross off multiples of odd numbers starting with 3 instead of 2.
-- 2. Only consider odd numbers up to \sqrt{n}, n being the limit.  The reason
-- is that any composite number m has a prime factor <= \sqrt{m}, so would be crossed off
-- by an odd number in the range [3, \sqrt{n}]:
-- Pf. n composite implies n = ab, with 1 < a,b < n.  Assume for contradiction that
-- a > \sqrt{n} and b > \sqrt{n}.  Then ab > (\sqrt{n})^2 = n, contradiction.
primeSieveBad :: Int -> [Int]
primeSieveBad lim =
  let lim' = ceiling $ sqrt $ fromIntegral lim
      odds = [3, 5.. lim']
      composites = do
        m <- odds
        n <- [m * m, m * m + 2 * m.. lim]
        pure n
  in (2 : [3, 5.. lim]) \\ composites


-- | A direct translation of a Python implementation.
-- This doesn't have improvements 1 and 2 above.
primeSieveAlsoBad :: Int -> [Int]
primeSieveAlsoBad lim = go 2 (V.replicate lim False) []
  where
    go n cs ps
      | n == lim  = ps
      | cs V.! n  = go (n + 1) cs ps
      | otherwise = go (n + 1) (update n (2 * n) cs) (n:ps)

    update n ix cs
      | ix >= lim = cs
      | otherwise = update n (ix + n) (cs V.// [(ix, True)])