{-# OPTIONS_GHC -O2 #-}
import Data. Array. ST
import Data. Array. Unboxed
main = do
-- let ps = primesTo (read w)
-- print (length ps, last ps) -- leaks badly
sieveUA top = runSTUArray $ do
sieve <- newArray ( 1 , m) True -- :: ST s (STUArray s Int Bool)
forM
_ [ 1 .. r `
div `
2 ] $ \i
-> do isPrime <- readArray sieve i
when isPrime $ -- ((2*i+1)^2-1)`div`2 = 2*i*(i+1)
forM_ [ 2 * i* ( i+ 1 ) , 2 * i* ( i+ 2 ) + 1 .. m] $ \j ->
writeArray sieve j False
primesTo top = 2 : [ i* 2 + 1 | ( i, True) <- assocs $ sieveUA top]
lastPrimes
:: Int -> ( Int , [ Int ] ) -- (nth, vals) lastPrimes top =
let arr = sieveUA top
( b, t) = bounds arr
in
( 1 + length [ ( ) | ( i
, True
) <- assocs arr
] , ( if ( top
< 13 ) then ( 2 :
) else id ) $ reverse $ take 5 [ 2 * i
+ 1 | i
<- [ t
, t
- 1 .. b
] , arr
! i
] )
{-
ST Array [Int] ON ODDS
-= n =- -= top =-
30,000: 350,377: 0.01s 3.7MB
100,000: 1,299,709: 0.03s 3.7MB
300,000: 4,256,233: 0.10s 3.7MB
1 mln --> 15,485,863: 0.43s 4.8MB time space (s_0=3.7)
2 mln --> 32,452,843: 0.98s 5.8MB
4 mln --> 67,867,967: 2.31s 8.9MB 1m-> n^1.21 n^1.12
5 mln --> 86,028,121: 3.04s 9.9MB
6 mln --> 104,395,301: 3.77s 10.9MB (leak: was: ***6.7s-227MB***!!!) ****
6,500,000-> 113,648,393: 4.14s 10.9MB
7 mln --> 122,949,823: 4.52s 11.9MB
7,538,613-> 133,000,999: 4.95s 11.9MB
8 mln --> 141,650,939: 5.32s 13.0MB 4m-> n^1.20 n^0.84
9 mln --> 160,481,183: 6.12s 14.0MB
10 mln --> 179,424,673: 6.91s 15.0MB
15 mln --> 275,604,541: 11.01s 21.1MB
18 mln --> 334,214,459: 13.65s 24.2MB 8m-> n^1.16 n^0.97 (1m->n^1.01)
20 mln --> 373,587,883: TIMEOUT
-}
ey0jIE9QVElPTlNfR0hDIC1PMiAjLX0KCmltcG9ydCBDb250cm9sLk1vbmFkCmltcG9ydCBDb250cm9sLk1vbmFkLlNUCmltcG9ydCBEYXRhLkFycmF5LlNUCmltcG9ydCBEYXRhLkFycmF5LlVuYm94ZWQKaW1wb3J0IERhdGEuQ2hhcgoKIAptYWluID0gZG8KICBzIDwtIGdldENvbnRlbnRzCiAgZm9yTV8gKHRha2VXaGlsZSAoaXNEaWdpdCAuIGhlYWQpICQgd29yZHMgcykgJCBcdy0+IGRvCiAgICAtLSBsZXQgcHMgPSBwcmltZXNUbyAocmVhZCB3KQogICAgLS0gcHJpbnQgKGxlbmd0aCBwcywgbGFzdCBwcykgICAgICAgIC0tIGxlYWtzIGJhZGx5CiAgICBwcmludCAobGFzdFByaW1lcyAocmVhZCB3KSkgICAgICAgICAgLS0gbm8gbGVhawogCnNpZXZlVUEgOjogSW50IC0+IFVBcnJheSBJbnQgQm9vbApzaWV2ZVVBIHRvcCA9IHJ1blNUVUFycmF5ICQgZG8KICAgIGxldCBtID0gKHRvcC0xKSBgZGl2YCAyCiAgICAgICAgciA9IGZsb29yIC4gc3FydCAuIGZyb21JbnRlZ3JhbCAkIHRvcCArIDEgCiAgICBzaWV2ZSA8LSBuZXdBcnJheSAoMSxtKSBUcnVlICAgICAgICAgICAgICAgICAtLSA6OiBTVCBzIChTVFVBcnJheSBzIEludCBCb29sKQogICAgZm9yTV8gWzEuLnIgYGRpdmAgMl0gJCBcaSAtPiBkbwogICAgICBpc1ByaW1lIDwtIHJlYWRBcnJheSBzaWV2ZSBpCiAgICAgIHdoZW4gaXNQcmltZSAkICAgICAgICAgICAgICAgICAgICAgICAgICAgICAtLSAoKDIqaSsxKV4yLTEpYGRpdmAyID0gMippKihpKzEpCiAgICAgICAgZm9yTV8gWzIqaSooaSsxKSwgMippKihpKzIpKzEuLm1dICQgXGogLT4gCiAgICAgICAgICB3cml0ZUFycmF5IHNpZXZlIGogRmFsc2UKICAgIHJldHVybiBzaWV2ZQogCnByaW1lc1RvIDo6IEludCAtPiBbSW50XQpwcmltZXNUbyB0b3AgPSAyIDogW2kqMisxIHwgKGksVHJ1ZSkgPC0gYXNzb2NzICQgc2lldmVVQSB0b3BdCiAKbGFzdFByaW1lcyA6OiBJbnQgLT4gKEludCxbSW50XSkgICAtLSAobnRoLCB2YWxzKQpsYXN0UHJpbWVzIHRvcCA9IAogIGxldCBhcnIgICA9IHNpZXZlVUEgdG9wCiAgICAgIChiLHQpID0gYm91bmRzIGFycgogIGluIAogICAgICggMSArIGxlbmd0aCBbKCkgfCAoaSxUcnVlKSA8LSBhc3NvY3MgYXJyXQogICAgICwgKGlmICh0b3AgPCAxMykgdGhlbiAoMjopIGVsc2UgaWQpIAogICAgICAgICQgcmV2ZXJzZSAkIHRha2UgNSBbIDIqaSsxIHwgaSA8LSBbdCx0LTEuLmJdLCBhcnIgISBpIF0gKQogCnstClNUIEFycmF5IFtJbnRdIE9OIE9ERFMgCiAgICAtPSBuID0tICAgIC09IHRvcCA9LSAKICAgIDMwLDAwMDogICAgIDM1MCwzNzc6ICAwLjAxcyAgMy43TUIKICAgMTAwLDAwMDogICAxLDI5OSw3MDk6ICAwLjAzcyAgMy43TUIKICAgMzAwLDAwMDogICA0LDI1NiwyMzM6ICAwLjEwcyAgMy43TUIKICAxIG1sbiAtLT4gIDE1LDQ4NSw4NjM6ICAwLjQzcyAgNC44TUIgICAgICAgIHRpbWUgICBzcGFjZSAoc18wPTMuNykKICAyIG1sbiAtLT4gIDMyLDQ1Miw4NDM6ICAwLjk4cyAgNS44TUIKICA0IG1sbiAtLT4gIDY3LDg2Nyw5Njc6ICAyLjMxcyAgOC45TUIgIDFtLT4gbl4xLjIxICBuXjEuMTIKICA1IG1sbiAtLT4gIDg2LDAyOCwxMjE6ICAzLjA0cyAgOS45TUIKICA2IG1sbiAtLT4gMTA0LDM5NSwzMDE6ICAzLjc3cyAxMC45TUIgICAobGVhazogd2FzOiAqKio2LjdzLTIyN01CKioqISEhKSAqKioqCjYsNTAwLDAwMC0+IDExMyw2NDgsMzkzOiAgNC4xNHMgMTAuOU1CCiAgNyBtbG4gLS0+IDEyMiw5NDksODIzOiAgNC41MnMgMTEuOU1CCjcsNTM4LDYxMy0+IDEzMywwMDAsOTk5OiAgNC45NXMgMTEuOU1CCiAgOCBtbG4gLS0+IDE0MSw2NTAsOTM5OiAgNS4zMnMgMTMuME1CICA0bS0+IG5eMS4yMCAgbl4wLjg0CiAgOSBtbG4gLS0+IDE2MCw0ODEsMTgzOiAgNi4xMnMgMTQuME1CCiAxMCBtbG4gLS0+IDE3OSw0MjQsNjczOiAgNi45MXMgMTUuME1CCiAxNSBtbG4gLS0+IDI3NSw2MDQsNTQxOiAxMS4wMXMgMjEuMU1CCiAxOCBtbG4gLS0+IDMzNCwyMTQsNDU5OiAxMy42NXMgMjQuMk1CICA4bS0+IG5eMS4xNiAgbl4wLjk3ICgxbS0+bl4xLjAxKQogMjAgbWxuIC0tPiAzNzMsNTg3LDg4MzogICAgVElNRU9VVCAgIAotfQ==