codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
module Main where main = do putStrLn "primes above 13,000,000,000:" let m = 13000000000 print $ take 8 $ primesFrom m let r = (floor.sqrt.fromIntegral) m k = length $ fst $ span (<= r) primes' (p:q:_) = drop (k-1) primes' print (r,k,[p,p*p,q,q*q]) primesFrom m = sieve (length h) ps $ m`div`2*2+1 where (h,(_:ps)) = span (<= (floor.sqrt.fromIntegral) m) primes primes = 2: 3: sieve 0 primes' 5 primes' = tail primes {- sieve k (p:ps) x -- only 5 billion (?) = [x | x<-[x,x+2..p*p-2], and [(x`rem`p)/=0 | p<-take k primes']] ++ sieve (k+1) ps (p*p+2) -} sieve k (p:ps) x -- only 14 billion (?) = let (h,t) = ([x,x+2..t-2],p*p) qs = take k primes' h' = filter (\x-> all ((/=0).(x`rem`)) qs) h in h' ++ sieve (k+1) ps (t+2)
Private
[
?
]
Run code
Submit