{-# OPTIONS_GHC -O2 #-}
module Main where
main = interact (\s-> show $ primes() !! (read s - 1))
primes :: () -> [Int ]
primes () = 2: primes' -- TREE-folding multiples-union
 where -- ERATOSthenes sieve
 primes' = 3: sieve primes' 5 9 []
 sieve (p:ps) x q fs = 
 ([x,x+2..q-2] `minus` 
 foldt [[y+s,y+2*s..q] | (s,y) <- fs])
 ++ sieve ps (q+2) (head ps^2)
 ((++ [(2*p,q)]) [(s,q-rem (q-y) s) | (s,y) <- fs])
 foldt (a:xs) = union a (foldt (pairs xs)) 
 foldt [] = []
 pairs (a:b:xs) = union a b : pairs xs
 pairs xs = xs
 union a@(x:xs) b@(y:ys) = case compare x y of 
 LT -> x : union xs b 
 EQ -> x : union xs ys
 GT -> y : union a ys
 union a [] = a
 union [] b = b
 minus a@(x:xs) b@(y:ys) = case compare x y of 
 LT -> x : minus xs b
 EQ -> minus xs ys
 GT -> minus a ys
 minus a b = a
{- FOLDT (w/ foldr) (w/ foldl)
 100,000: 1,299,709 0.23s 6.8MB 0.40s 7.8MB 1.33s 8.8MB
 0.5 mln: 7,368,787 1.54s 25.2MB 3.80s 31.3MB 300k:7.35s 19MB
 1.0 mln: 15,485,863 3.65s 48.8MB 10.31s 57.0MB 450k:14.1s 28MB
 2.0 mln: 32,452,843 8.74s 110.2MB 
 2.5 mln: 41,161,739 12.02s 134.8MB
 O(n^1.28) O(n^1.1) (n^1.41) (n^1.3) (n^1.57) (^2.1)
-}

ey0jIE9QVElPTlNfR0hDIC1PMiAjLX0KbW9kdWxlIE1haW4gd2hlcmUKCm1haW4gPSBpbnRlcmFjdCAoXHMtPiBzaG93ICQgcHJpbWVzKCkgISEgKHJlYWQgcyAtIDEpKQoKcHJpbWVzIDo6ICgpIC0+IFtJbnRdCnByaW1lcyAoKSA9IDI6IHByaW1lcycgICAtLSBUUkVFLWZvbGRpbmcgbXVsdGlwbGVzLXVuaW9uCiB3aGVyZSAgICAgICAgICAgICAgICAgICAtLSAgRVJBVE9TdGhlbmVzIHNpZXZlCiAgIHByaW1lcycgID0gMzogc2lldmUgcHJpbWVzJyA1IDkgW10KICAgc2lldmUgKHA6cHMpIHggcSBmcyA9IAogICAgICAgIChbeCx4KzIuLnEtMl0gYG1pbnVzYCAKICAgICAgICAgICAgICAgICAgICAgICAgICBmb2xkdCBbW3krcyx5KzIqcy4ucV0gfCAocyx5KSA8LSBmc10pCiAgICAgICAgKysgc2lldmUgcHMgKHErMikgKGhlYWQgcHNeMikKICAgICAgICAgICAgICgoKysgWygyKnAscSldKSBbKHMscS1yZW0gKHEteSkgcykgfCAocyx5KSA8LSBmc10pCiAgICAKICAgZm9sZHQgKGE6eHMpICAgICA9IHVuaW9uIGEgKGZvbGR0IChwYWlycyB4cykpIAogICBmb2xkdCBbXSAgICAgICAgID0gW10KICAgcGFpcnMgKGE6Yjp4cykgICA9IHVuaW9uIGEgYiA6IHBhaXJzIHhzCiAgIHBhaXJzIHhzICAgICAgICAgPSB4cwogICAKICAgdW5pb24gYUAoeDp4cykgYkAoeTp5cykgPSBjYXNlIGNvbXBhcmUgeCB5IG9mIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgTFQgLT4geCA6IHVuaW9uIHhzIGIgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBFUSAtPiB4IDogdW5pb24geHMgeXMKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIEdUIC0+IHkgOiB1bmlvbiBhICB5cwogICB1bmlvbiBhICAgICAgICBbXSAgICAgICA9IGEKICAgdW5pb24gW10gICAgICAgYiAgICAgICAgPSBiCiAgIAogICBtaW51cyBhQCh4OnhzKSBiQCh5OnlzKSA9IGNhc2UgY29tcGFyZSB4IHkgb2YgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBMVCAtPiB4IDogbWludXMgeHMgYgogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgRVEgLT4gICAgIG1pbnVzIHhzIHlzCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBHVCAtPiAgICAgbWludXMgYSAgeXMKICAgbWludXMgYSAgICAgICAgYiAgICAgICAgPSBhCiAgIAp7LSAgICAgICAgICAgICAgICAgICAgICAgICAgIEZPTERUICAgICAgICAgICAgKHcvIGZvbGRyKSAgICAgICAgKHcvIGZvbGRsKQogICAxMDAsMDAwOiAgMSwyOTksNzA5ICAgMC4yM3MgICAgNi44TUIgICAgICAwLjQwcyAgIDcuOE1CICAgICAgMS4zM3MgIDguOE1CCiAgIDAuNSBtbG46ICA3LDM2OCw3ODcgICAxLjU0cyAgIDI1LjJNQiAgICAgIDMuODBzICAzMS4zTUIgICAgMzAwazo3LjM1cyAxOU1CCiAgIDEuMCBtbG46IDE1LDQ4NSw4NjMgICAzLjY1cyAgIDQ4LjhNQiAgICAgMTAuMzFzICA1Ny4wTUIgICAgNDUwazoxNC4xcyAyOE1CCiAgIDIuMCBtbG46IDMyLDQ1Miw4NDMgICA4Ljc0cyAgMTEwLjJNQiAgCiAgIDIuNSBtbG46IDQxLDE2MSw3MzkgIDEyLjAycyAgMTM0LjhNQgogICAKICAgICAgICAgICAgICAgICAgICAgTyhuXjEuMjgpICBPKG5eMS4xKSAgIChuXjEuNDEpIChuXjEuMykgICAobl4xLjU3KSAoXjIuMSkKLX0=

comments (?)

MTAwMDAwMA==

1000000

[1 of 1] Compiling Main ( prog.hs, prog.o )
Linking prog ...

15485863

https://ideone.com/pfREP

Share or Embed source code

<script src="https://ideone.com/e.js/pfREP" type="text/javascript" ></script>

Global

Ace editor

Textarea