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