{-# OPTIONS_GHC -O2 #-}
module Main where
import Data.Array.Unboxed
case spec of
-- [n] -> print . take 10 . drop (n-10) $ primesTMWE
[n
,lim
] -> print $ primesLimAOE lim n
-- array-based Sieve of Eratosthenes, using an array that is passed as
-- an accumulating argument between steps of iterative computation, and
-- as such is liable to the destructive update (doesn't happen, but still is fast,
-- on unboxed arrays, with explicit type signature, GHC-compiled with -O2),
-- working with odds only (original: ideone.com/dE0iU)
primesLimAOE m n
| m
> 2 = sieve
3 ( accumArray
const True
(1,m2
) [] ) where
sieve p a
| p > r = let k = 10
(l,u) = bounds a
len
= 1 + length [() | (i
,True
) <- assocs a
] ixs
= reverse $ take (len
-n
+k
) [i
| i
<-[u
,u
-1..l
], a
!i
] last = (if len
< n
then [2] else []) ++ [2*i
+1 | i
<- take k ixs
] | a!p2 = sieve (p+2) $ a//[(i,False) | i <- [q2, q2+p..m2]]
-- 2017: NB: newer compiler currently in use runs this code almost 3x faster.
-- abPSOx-derived code (for odds, that is) might be faster.
-- 1m:78498:0.04-4.8 2750159:200k:0.09-4.8 5800079:400k:0.21-5.8 15485863:1m:0.67-7.8 32452843:2m:2.16-11.9
-- 67867967:4m:5.63-24.2 104395301:6m:9.84-39.6 122949823:7m:12.20-36.5 141650939:8m:14.61-40.6
ey0jIE9QVElPTlNfR0hDIC1PMiAjLX0KCm1vZHVsZSBNYWluIHdoZXJlCgppbXBvcnQgRGF0YS5BcnJheS5VbmJveGVkCgptYWluICA9IGRvIHNwZWMgPC0gbWFwIHJlYWQgLiB0YWtlIDIgLiB3b3JkcyA8JD4gZ2V0TGluZSAgCiAgICAgICAgICAgY2FzZSBzcGVjIG9mICAKICAgICAgICAgICAgIC0tIFtuXSAgICAgLT4gcHJpbnQgLiB0YWtlIDEwIC4gZHJvcCAobi0xMCkgJCBwcmltZXNUTVdFIAogICAgICAgICAgICAgW24sbGltXSAtPiBwcmludCAkIHByaW1lc0xpbUFPRSBsaW0gbgoKLS0gYXJyYXktYmFzZWQgU2lldmUgb2YgRXJhdG9zdGhlbmVzLCB1c2luZyBhbiBhcnJheSB0aGF0IGlzIHBhc3NlZCBhcyAKLS0gYW4gYWNjdW11bGF0aW5nIGFyZ3VtZW50IGJldHdlZW4gc3RlcHMgb2YgaXRlcmF0aXZlIGNvbXB1dGF0aW9uLCBhbmQgCi0tIGFzIHN1Y2ggaXMgbGlhYmxlIHRvIHRoZSBkZXN0cnVjdGl2ZSB1cGRhdGUgKGRvZXNuJ3QgaGFwcGVuLCBidXQgc3RpbGwgaXMgZmFzdCwgIAotLSBvbiB1bmJveGVkIGFycmF5cywgd2l0aCBleHBsaWNpdCB0eXBlIHNpZ25hdHVyZSwgR0hDLWNvbXBpbGVkIHdpdGggLU8yKSwgIAotLSB3b3JraW5nIHdpdGggb2RkcyBvbmx5ICAgICAgICAgKG9yaWdpbmFsOiBpZGVvbmUuY29tL2RFMGlVKQoKcHJpbWVzTGltQU9FIDo6IEludCAtPiBJbnQgLT4gKEludCxbSW50XSkKcHJpbWVzTGltQU9FIG0gbiB8IG0gPiAyID0gc2lldmUgMyAoIGFjY3VtQXJyYXkgY29uc3QgVHJ1ZSAoMSxtMikgW10gKQogIHdoZXJlCiAgICBtMiA9IChtLTEpIGBkaXZgIDIKICAgIHIgID0gZmxvb3IgLiBzcXJ0ICQgZnJvbUludGVncmFsIG0gKyAxCiAgICBzaWV2ZSA6OiBJbnQgLT4gVUFycmF5IEludCBCb29sIC0+IChJbnQsIFtJbnRdKSAgLS0gMjAxNzogbW92ZWQgdHlwZSBkZWNsIGhlcmUKICAgIHNpZXZlIHAgYSAKICAgICAgfCBwID4gciAgPSBsZXQgIGsgPSAxMAogICAgICAgICAgICAgICAgICAgICAgKGwsdSkgPSBib3VuZHMgYQogICAgICAgICAgICAgICAgICAgICAgbGVuICAgPSAxICsgbGVuZ3RoIFsoKSB8IChpLFRydWUpIDwtIGFzc29jcyBhXSAgCiAgICAgICAgICAgICAgICAgICAgICBpeHMgICA9IHJldmVyc2UgJCB0YWtlIChsZW4tbitrKSBbaSB8IGk8LVt1LHUtMS4ubF0sIGEhaV0KICAgICAgICAgICAgICAgICAgICAgIGxhc3QgID0gKGlmIGxlbiA8IG4gdGhlbiBbMl0gZWxzZSBbXSkgKysKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgWzIqaSsxIHwgaSA8LSB0YWtlIGsgaXhzXQogICAgICAgICAgICAgICAgICAgIGluICAgKCBsZW4sIGxhc3QgKQogICAgICB8IGEhcDIgICAgICA9IHNpZXZlIChwKzIpICQgYS8vWyhpLEZhbHNlKSB8IGkgPC0gW3EyLCBxMitwLi5tMl1dCiAgICAgIHwgb3RoZXJ3aXNlID0gc2lldmUgKHArMikgYQogICAgICAgICAgICAgICAgICAgICAgIHdoZXJlIHAyID0gKHAtMSkgYGRpdmAgMgogICAgICAgICAgICAgICAgICAgICAgICAgICAgIHEyID0gKHAqcC0xKSBgZGl2YCAyCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgCi0tIDIwMTc6IE5COiBuZXdlciBjb21waWxlciBjdXJyZW50bHkgaW4gdXNlIHJ1bnMgdGhpcyBjb2RlIGFsbW9zdCAzeCBmYXN0ZXIuCi0tICAgICAgIGFiUFNPeC1kZXJpdmVkIGNvZGUgKGZvciBvZGRzLCB0aGF0IGlzKSBtaWdodCBiZSBmYXN0ZXIuCgotLSAxbTo3ODQ5ODowLjA0LTQuOCAyNzUwMTU5OjIwMGs6MC4wOS00LjggNTgwMDA3OTo0MDBrOjAuMjEtNS44IDE1NDg1ODYzOjFtOjAuNjctNy44IDMyNDUyODQzOjJtOjIuMTYtMTEuOQoKLS0gNjc4Njc5Njc6NG06NS42My0yNC4yIDEwNDM5NTMwMTo2bTo5Ljg0LTM5LjYgMTIyOTQ5ODIzOjdtOjEyLjIwLTM2LjUgMTQxNjUwOTM5OjhtOjE0LjYxLTQwLjY=
MTAwMDAwMCAxNTQ4NTg2MyAgICAob2xkZXIgSWRlb25lIHVzZWQgR0hDICg2LjguLi4uKSkKNDAwMDAwIDU4MDAwNzkgICAgIChub3cgaXQncyB0d2ljZSBzbG93ZXIsIHdpdGggR0hDICg3LjYuMykgLi4uPyk=
1000000 15485863 (older Ideone used GHC (6.8....))
400000 5800079 (now it's twice slower, with GHC (7.6.3) ...?)
(1000000,[15485761,15485773,15485783,15485801,15485807,15485837,15485843,15485849,15485857,15485863])