import System.Environment
import Control.Monad
import Text.PrettyPrint
-- genuine sieve and filter, but with run-length encoding for zeros
genuineRLC = 2 : [ x | Right x <- (foldr sieve id genuineRLC (map Right [0..])), x>2 ]
where
sieve p f xs@(Right off:_) = Left 1: tail (applyAt (p*p-off) (f . sieve' p) xs)
sieve' p = applyAt p (\(b:bs)->sieve' p (either Left (const (Left 1)) b:bs))
applyAt 0 f xs = f xs
applyAt n f (Right x:xs) = Right x:applyAt (n-1) f xs
applyAt n f (Left x:xs) | x<=n = merge $ Left x:applyAt (n-x) f xs
| otherwise = merge $ Left n:applyAt 0 f (Left (x-n):xs)
merge (Left n1:Left n2:xs) = merge (Left (n1+n2):xs)
merge xs = xs
-- "genuine" sieve (zero out non-primes) and filter (remove dross)
-- start sieve for p at position p*p, zeroing position off=(p-1)*(p-1),
-- then zero positions that are multiples of p
genuine = 2 : filter (>2) (foldr sieve id genuine [0..])
sieve p f xs@(off:_) = 0: tail (applyAt (p*p-off) (f . sieve' p) xs)
sieve' p = applyAt p (\(_:b)->sieve' p (0:b))
applyAt 0 f xs = f xs
applyAt n f (x:xs) = x:applyAt (n-1) f xs
-- optimized folklore, with explicitly merged sieves, rather than implictly thunked ones
folklore3 pns xs = x : folklore3 (insert (x,x*x) pns') xs'
where (x,pns',xs') = sieve3 pns xs
sieve3 ((p,n):pns) (x:xs) | xn]++xs)
sieve3 [] (x:xs) = (x,[],xs)
insert (p,n) [] = [(p,n)]
insert (p,n) ((p',n'):pns) | n<=n' = (p,n):(p',n'):pns
| otherwise = (p',n'):insert (p,n) pns
-- optimized folklore, sieves filter by comparing to multiples of p, starting at p*p
folklore2 (x:xs) = x : folklore2 (sieve2 x (x*x) xs)
sieve2 p n (x:xs) | xn]++xs)
-- folklore, sieves filter with mod
folklore (x:xs) = x : folklore [ p | p <- xs, p `mod` x > 0 ]
-- faster, "dual" version; test against small enough primes
-- (dual, because instead of constructing sieves from primes,
-- it observes the effect of those prime sieves)
dual = 2: [x | x <-[3,5..], all (\p -> x `mod` p > 0) (factorsToTry x)]
where factorsToTry x = takeWhile (\p -> p*p <= x) dual
main = do
(n':which:_) <- getArgs
let n = read n'::Int
print $ (,) n $ (!!n) $ maybe (error "unknown variant") id $ lookup which variants
where variants = -- 10^4 10^5 10^6
[("folklore" , 2 : folklore [3,5..] ) -- 8.8
,("folklore2" , 2 : folklore2 [3,5..] ) -- 5.3
,("folklore3" , 2 : folklore3 [] [3,5..] ) -- 0.58 51.5
,("genuine" , genuine ) -- 0.43 8.7 5m17
,("genuineRLC", genuineRLC ) -- 0.33 3.6 1m27
,("dual" , dual ) -- 0.25 2.5 1m0
]
-- translation:-) folklore->sieve; genuine->Reinke; dual->naive
-- (timings: ghc-6.4.1 -O, on a 2ghz pentium m760, 1gb ram, win xp)