{-# OPTIONS_GHC -O2 -fno-cse #-} main = getLine >>= print . (primes !!) . (+ (-1)) . read primes :: [Int] -- wheeled gaps on treefold-joined wheeled primes' multiples primes = 2:3:5:7: gaps 11 wheel (join $ roll 11 wheel primes_) where primes_ = 11: gaps 13 (tail wheel) (join $ roll 11 wheel primes_) gaps k ws@(w:t) cs@(c:u) | k==c = gaps (k+w) t u | True = k : gaps (k+w) t cs -- kc+p*d) (p*p) ws : roll (k+w) t u | True = roll (k+w) t ps -- k

x: union xs b EQ -> x: union xs ys GT -> y: union a ys {- Tree Merged Multiples Re-moval: O(n^1.24) speed, O(1) space: --- simple_tfold ---- two-feed ------ wheel ------ 3/2 tfold -- gaps/roll 1M 4.09s _47.8MB -- 3.28s 4.7MB -- 1.95s 5.8MB -- 1.90s 4.8MB -- 1.38s --- 2M 9.86s 111.2MB -- 7.66s 4.7MB -- 4.68s 5.8MB -- 4.48s 4.8MB -- 3.25s --- 3M ------------------------------------------------------------- 5.40s --- 4M 7.68s - 4.7M 5M 10.08s - 4.7M 6M 12.66s - 4.7M O(n^1.24) -} main2 = mapM_ print $ zipWith logBase (map (6/) [1..5]) (map (12.66/) [1.38,3.25,5.40,7.68,10.08])