fork(1) download
copy 
  1.  {-# OPTIONS_GHC -O2 -fno-cse #-}
  2. main = getLine >>= print . (primes !!) . (+ (-1)) . read
  3.  
  4. primes :: [Int]  -- wheeled gaps on treefold-joined wheeled primes' multiples
  5. primes = 2:3:5:7: gaps 11 wheel (join $ roll 11 wheel primes_)
  6.  where
  7.    primes_ = 11: gaps 13 (tail wheel) 
  8.                                 (join $ roll 11 wheel primes_)
  9.  
  10.    gaps k ws@(w:t) cs@(c:u) | k==c  = gaps (k+w) t u 
  11.                             | True  = k : gaps (k+w) t cs     -- k<c
  12.  
  13.    roll k ws@(w:t) ps@(p:u) | k==p  = scanl (\c d->c+p*d) (p*p) ws 
  14.                                         : roll (k+w) t u 
  15.                             | True  = roll (k+w) t ps         -- k<p 
  16.  
  17.    join ((x:xs): ~(ys:zs:t)) = x : union xs (union ys zs)    
  18.                                       `union` join (pairs t)  
  19.    pairs ((x:xs):ys:t)       = (x : union xs ys) : pairs t
  20.  
  21.    wheel = 2:4:2:4:6:2:6:4:2:4:6:6:2:6:4:2:6:4:6:8:4:2:4:2:
  22.            4:8:6:4:6:2:4:6:2:6:6:4:2:4:6:2:6:4:2:4:2:10:2:10:wheel
  23.  
  24.    union a@(x:xs) b@(y:ys) = case compare x y of
  25.       LT -> x: union xs b
  26.       EQ -> x: union xs ys
  27.       GT -> y: union a  ys
  28. {-
  29. Tree Merged Multiples Re-moval:  O(n^1.24) speed, O(1) space:
  30.  
  31. --- simple_tfold ---- two-feed ------ wheel ------ 3/2 tfold -- gaps/roll
  32. 1M 4.09s _47.8MB -- 3.28s 4.7MB -- 1.95s 5.8MB -- 1.90s 4.8MB -- 1.38s ---
  33. 2M 9.86s 111.2MB -- 7.66s 4.7MB -- 4.68s 5.8MB -- 4.48s 4.8MB -- 3.25s ---
  34. 3M ------------------------------------------------------------- 5.40s ---
  35. 4M                                                               7.68s - 4.7M
  36. 5M                                                              10.08s - 4.7M
  37. 6M                                                              12.66s - 4.7M
  38.  
  39.                                                                O(n^1.24)
  40. -}
  41.  
  42. main2 = mapM_ print $ zipWith logBase (map (6/) [1..5])
  43.                       (map (12.66/) [1.38,3.25,5.40,7.68,10.08])
  44.  
stdin
copy 
1000000
compilation info 
[1 of 1] Compiling Main             ( prog.hs, prog.o )
Linking prog ...
stdout
copy 
15485863
https://ideone.com/Ojq01
language:
Haskell (ghc 8.4.4)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!