Skip to content

Instantly share code, notes, and snippets.

@neetsdkasu
Created Nov 17, 2018
Embed
What would you like to do?
Primes ( Haskell ) (酷いw)
-- author: Leonardne @ NEETSDKASU
import qualified Data.IntSet as IS
hoge p = [p,p+p..]
fuga p = unzip . map (break (> p))
piyo (s, e, xs) =
case IS.minView s of
Nothing -> piyo $ foo e xs
Just (p, t) -> p : piyo (bar p t e xs)
foo e xs = (t, r, ys)
where
r = e+100000
s = IS.fromList [e+2,e+4..r]
(d, ys) = fuga r xs
t = foldl (foldl (flip IS.delete)) s d
bar p s e xs = (t, e, ys)
where
(d, ps) = break (> e) $ hoge p
t = foldl (flip IS.delete) s d
ys = ps:xs
baz = 2 : 3 : piyo (IS.empty, 3, [hoge 3])
main = print $ take 100 $ drop 19950 $ baz
@neetsdkasu
Copy link
Author

neetsdkasu commented Nov 17, 2018

IDEONEで実行してみた
10万個が1秒くらいだた
https://ideone.com/cIK9Xv

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment