1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 {-# OPTIONS_GHC -O2 -fno-cse #-}
main = getLine >>= print . (primes !!) . (+ (-1)) . read
 
data People a = VIP a (People a) | Crowd [a]
 
primes :: [Int]
primes = 2:3:5:7: gaps 11 wheel (join $ roll 11 wheel primes')
 where
   primes' = 11:13:17:19:23:29:31: gaps 37 (drop 7 wheel) 
                                (join $ roll 11 wheel primes')
 
   gaps k (w:t) cs@(VIP c u) | k==c  = gaps (k+w) t u 
                             | True  = k : gaps (k+w) t cs     -- k<c
 
   roll k ws@(w:t) ps@(p:u)  | k==p  = vips (scanl (\c d->c+p*d) (p*p) ws)
                                         : roll (k+w) t u 
                             | True  = roll (k+w) t ps         -- k<p 
 
   join (xs:ys:zs:t) = unionP xs (unionP ys zs)               -- ~(ys:zs:t) w/VIPs causes memory leak
                                      `unionP` join (pairs t) -- strict pat must have more defined primes'
   pairs (xs:ys:t)   = unionP xs ys : pairs t
    
   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:
           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
   
   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
   
   vips (x:t) = VIP x $ Crowd t
 
   unionP :: Ord a => People a -> People a -> People a
   unionP (VIP x  t) ys                  = VIP x $ unionP t ys
   unionP (Crowd xs) (Crowd ys)          = Crowd $ union xs ys
   unionP xs@(Crowd (x:t)) ys@(VIP y w)  = case compare x y of
      LT -> VIP x $ unionP (Crowd t) ys
      EQ -> VIP x $ unionP (Crowd t) w
      GT -> VIP y $ unionP xs        w
 
{-
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.66-4.7
5M                                                              10.16-4.7
6M                                                              12.71-4.7
                             ********
    vips/minus   vips~gaps   vips/gaps
1M   1.95-4.8    1.41-5.8    1.46-4.8
2M   4.53-4.8    3.51-10.9   3.36-4.8
3M   7.45-4.8    5.70-12.9   5.55-4.8
4M  10.71-4.8                7.92-4.8
5M  13.98-4.8               10.40-4.8
6M                          12.99-4.8
-}

IHstIyBPUFRJT05TX0dIQyAtTzIgLWZuby1jc2UgIy19Cm1haW4gPSBnZXRMaW5lID4+PSBwcmludCAuIChwcmltZXMgISEpIC4gKCsgKC0xKSkgLiByZWFkCgpkYXRhIFBlb3BsZSBhID0gVklQIGEgKFBlb3BsZSBhKSB8IENyb3dkIFthXQogCnByaW1lcyA6OiBbSW50XQpwcmltZXMgPSAyOjM6NTo3OiBnYXBzIDExIHdoZWVsIChqb2luICQgcm9sbCAxMSB3aGVlbCBwcmltZXMnKQogd2hlcmUKICAgcHJpbWVzJyA9IDExOjEzOjE3OjE5OjIzOjI5OjMxOiBnYXBzIDM3IChkcm9wIDcgd2hlZWwpIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIChqb2luICQgcm9sbCAxMSB3aGVlbCBwcmltZXMnKQoKICAgZ2FwcyBrICh3OnQpIGNzQChWSVAgYyB1KSB8IGs9PWMgID0gZ2FwcyAoayt3KSB0IHUgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgfCBUcnVlICA9IGsgOiBnYXBzIChrK3cpIHQgY3MgICAgIC0tIGs8YwoKICAgcm9sbCBrIHdzQCh3OnQpIHBzQChwOnUpICB8IGs9PXAgID0gdmlwcyAoc2NhbmwgKFxjIGQtPmMrcCpkKSAocCpwKSB3cykKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICA6IHJvbGwgKGsrdykgdCB1IAogICAgICAgICAgICAgICAgICAgICAgICAgICAgIHwgVHJ1ZSAgPSByb2xsIChrK3cpIHQgcHMgICAgICAgICAtLSBrPHAgCgogICBqb2luICh4czp5czp6czp0KSA9IHVuaW9uUCB4cyAodW5pb25QIHlzIHpzKSAgICAgICAgICAgICAgIC0tIH4oeXM6enM6dCkgdy9WSVBzIGNhdXNlcyBtZW1vcnkgbGVhawogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGB1bmlvblBgIGpvaW4gKHBhaXJzIHQpIC0tIHN0cmljdCBwYXQgbXVzdCBoYXZlIG1vcmUgZGVmaW5lZCBwcmltZXMnCiAgIHBhaXJzICh4czp5czp0KSAgID0gdW5pb25QIHhzIHlzIDogcGFpcnMgdAogICAgCiAgIHdoZWVsID0gMjo0OjI6NDo2OjI6Njo0OjI6NDo2OjY6Mjo2OjQ6Mjo2OjQ6Njo4OjQ6Mjo0OjI6CiAgICAgICAgICAgNDo4OjY6NDo2OjI6NDo2OjI6Njo2OjQ6Mjo0OjY6Mjo2OjQ6Mjo0OjI6MTA6MjoxMDp3aGVlbAogICAKICAgdW5pb24gYUAoeDp4cykgYkAoeTp5cykgPSBjYXNlIGNvbXBhcmUgeCB5IG9mCiAgICAgIExUIC0+IHg6IHVuaW9uIHhzIGIKICAgICAgRVEgLT4geDogdW5pb24geHMgeXMKICAgICAgR1QgLT4geTogdW5pb24gYSAgeXMKICAgCiAgIHZpcHMgKHg6dCkgPSBWSVAgeCAkIENyb3dkIHQKCiAgIHVuaW9uUCA6OiBPcmQgYSA9PiBQZW9wbGUgYSAtPiBQZW9wbGUgYSAtPiBQZW9wbGUgYQogICB1bmlvblAgKFZJUCB4ICB0KSB5cyAgICAgICAgICAgICAgICAgID0gVklQIHggJCB1bmlvblAgdCB5cwogICB1bmlvblAgKENyb3dkIHhzKSAoQ3Jvd2QgeXMpICAgICAgICAgID0gQ3Jvd2QgJCB1bmlvbiB4cyB5cwogICB1bmlvblAgeHNAKENyb3dkICh4OnQpKSB5c0AoVklQIHkgdykgID0gY2FzZSBjb21wYXJlIHggeSBvZgogICAgICBMVCAtPiBWSVAgeCAkIHVuaW9uUCAoQ3Jvd2QgdCkgeXMKICAgICAgRVEgLT4gVklQIHggJCB1bmlvblAgKENyb3dkIHQpIHcKICAgICAgR1QgLT4gVklQIHkgJCB1bmlvblAgeHMgICAgICAgIHcKCnstClRyZWUgTWVyZ2VkIE11bHRpcGxlcyBSZS1tb3ZhbDogIE8obl4xLjI0KSBzcGVlZCwgTygxKSBzcGFjZToKCi0tLSBzaW1wbGVfdGZvbGQgLS0tLSB0d28tZmVlZCAtLS0tLS0gd2hlZWwgLS0tLS0tIDMvMiB0Zm9sZCAtLSBnYXBzL3JvbGwgCjFNIDQuMDlzIF80Ny44TUIgLS0gMy4yOHMgNC43TUIgLS0gMS45NXMgNS44TUIgLS0gMS45MHMgNC44TUIgLS0gMS4zOHMgLS0tCjJNIDkuODZzIDExMS4yTUIgLS0gNy42NnMgNC43TUIgLS0gNC42OHMgNS44TUIgLS0gNC40OHMgNC44TUIgLS0gMy4yNXMgLS0tCjNNIC0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0gNS40MHMgLS0tCjRNICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgNy42Ni00LjcKNU0gICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIDEwLjE2LTQuNwo2TSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgMTIuNzEtNC43CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgKioqKioqKioKICAgIHZpcHMvbWludXMgICB2aXBzfmdhcHMgICB2aXBzL2dhcHMKMU0gICAxLjk1LTQuOCAgICAxLjQxLTUuOCAgICAxLjQ2LTQuOAoyTSAgIDQuNTMtNC44ICAgIDMuNTEtMTAuOSAgIDMuMzYtNC44CjNNICAgNy40NS00LjggICAgNS43MC0xMi45ICAgNS41NS00LjgKNE0gIDEwLjcxLTQuOCAgICAgICAgICAgICAgICA3LjkyLTQuOAo1TSAgMTMuOTgtNC44ICAgICAgICAgICAgICAgMTAuNDAtNC44CjZNICAgICAgICAgICAgICAgICAgICAgICAgICAxMi45OS00LjgKLX0=