Skip to content

Instantly share code, notes, and snippets.

@turnage
Created January 27, 2020 03:23
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save turnage/be75f5cab2d03728b4b7482f6e287563 to your computer and use it in GitHub Desktop.
Save turnage/be75f5cab2d03728b4b7482f6e287563 to your computer and use it in GitHub Desktop.
Simple Prime Sieve
data Sieve = Sieve
{ limit :: Int
, position :: Int
, product :: Int
, sieve :: [Int]
, count :: Int
}
uniquePrimes :: Sieve -> Maybe (Int, Sieve)
uniquePrimes (Sieve limit position product sieve count) = if product * position > limit
then Nothing
else if isPrime position
then let count' = count + 1
product' = product * position
in Just $ (count', Sieve limit position' product' (position : sieve) count')
else uniquePrimes $ Sieve limit position' product sieve count
where
position' = position + 1
isPrime c = not $ any (\p -> c `mod` p == 0) sieve
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment