Guest User

Sieve Of Eratosthenes

a guest
Jun 17th, 2016
182
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import qualified Data.IntSet as S
  2. primesUpTo :: Int -> [Int]
  3. primesUpTo n = 2 : put S.empty [3,5..n]
  4.     where put :: S.IntSet -> [Int] -> [Int]
  5.           put _ [] = []
  6.           put comps (x:xs) =
  7.             if S.member x comps
  8.             then put comps xs
  9.             else x : put (S.union comps multiples) xs
  10.                 where multiples = S.fromList [x*2, x*3 .. n]
  11. primesUpTo' :: Int -> [Int]
  12. primesUpTo' n = takeWhile (<n) $ sieve [2..]
  13.     where sieve (p:xs) = p : sieve [x | x <- xs, mod x p /= 0]
  14. main = putStrLn . show . last . primesUpTo . read $ "2000000" -- =<< getLine
Add Comment
Please, Sign In to add comment