Skip to content

Instantly share code, notes, and snippets.

@begriffs

begriffs/primesTo.hs

Created December 23, 2015 08:12
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save begriffs/46c9e47e7c5a6a1afd62 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save begriffs/46c9e47e7c5a6a1afd62 to your computer and use it in GitHub Desktop.
Download ZIP
Calculating list of primes less than n
Raw
primesTo.hs
primesTo :: Int -> [Int]
primesTo n = removeHeadMultiples [2..n]
where
removeHeadMultiples same@(p:xs)
| p*p > n = same -- short circuit factors greater than sqrt(n)
| otherwise = p : removeHeadMultiples [x | x <- xs, x `rem` p > 0]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment