User:WillNess/Haskell primes one-liners

Was here.

Prime numbers

edit

One-liners:

[n | n<-[2..], not $ elem n [j*k | j<-[2..n-1], k<-[2..n-1]]]
[n | n<-[2..], not $ elem n [j*k | j<-[2..n`div`2], k<-[2..min j (n`div`j)]]]
[n | n<-[2..], foldl (\a b-> a && (rem n b > 0)) True [2..n-1]]
[n | n<-[2..], all ((> 0).rem n) [2..n-1]]
[n | n<-2:[3,5..], all ((> 0).rem n) [3,5..(floor.sqrt.fromIntegral) n]]

let { ps = 2:foldr (\i-> (i:).(`minus` map (i*) (foldr (\p r->if (p<i && mod i p>0) 
                                   then (p:r) else [p]) [] ps))) [] [3,5..] } in ps 

foldr (\n->(n:).filter ((> 0).(`rem`n))) [] [2..]
map head $ iterate (\(x:t)-> minus t $ [x*x, x*x+x..]) [2..]
map head $ iterate (\(x:t)-> minus t $ map (*x) (x:t)) [2..]
map head $ iterate (\(x:t)-> filter ((> 0).(`rem`x)) t) [2..]
2 : unfoldr (\(x:t)-> Just(x, filter ((> 0).(`rem`x)) t)) [3,5..]

\n -> foldl (\r x-> r `minus` [x*x, x*x+x..]) [2..n] [2..(floor.sqrt.fromIntegral) n]
2 : concat (unfoldr (\(ns,x:xs)-> let (h,r)=span (< x*x) ns in 
                             Just (h, (r `minus` [x*x, x*x+2*x..], xs))) ([3,5..], [3,5..]))
2 : minus [3,5..] (foldi (\(x:xs)->(x:).union xs) [] $ map (\x->[x*x, x*x+2*x..]) [3,5..])

\n-> let {second f (a,b)=(a,f b) ; ans=concatMap fst . scanl (\(_,qs) p-> second 
  (`minus`[p*p, p*p+2*p..]) $ span (<p*p) qs) ([3],[5,7..n]) . 
  foldr (\x r->if x^2>n then [x] else x:r) [] $ ans} in 2:ans

nubBy (((==0).).rem) [2..]

let ps = 2 : [n | n<-[3..], all ((> 0).rem n) $ takeWhile ((<= n).(^2)) ps] in ps
let ps = 3 : [n | n<-[5,7..], foldr (\p r-> p*p>n || (rem n p>0 && r)) True ps] in 2 : ps

\n -> 2 : foldr (\r z-> if (head r^2) <= n then head r : z else r) []  
                (let rs=[3,5..n] : [t `minus` [p*p, p*p+2*p..] | (p:t)<- rs] in rs)
let ps = 3 : concat (unfoldr (\(xs,p:ps)-> let (h,t)=span (< p*p) xs in 
                  Just (h, (t `minus` [p*p, p*p+2*p..], ps))) ([5,7..], ps)) in 2 : ps

let { sieve (x:xs) = x : sieve [n | n <- xs, rem n x > 0] } in sieve [2..] 
let { sieve xs (p:ps) = let (h,t)=span (< p*p) xs in h++sieve (filter ((> 0).(`rem`p)) t) ps 
    ; primes = 3 : sieve [5,7..] primes } in 2 : primes  
let { sieve xs (p:ps) = let (h,t)=span (< p*p) xs in h++sieve (t `minus` [p*p, p*p+2*p..]) ps 
    ; primes = 3 : sieve [5,7..] primes } in 2 : primes

let ps = 2 : minus [3..] (foldr (\p r-> p*p:union [p*p+p, p*p+2*p..] r) [] ps) in ps

fix((2:).minus [3..].foldr (\p-> (p*p:).union [p*p+p, p*p+2*p..]) [])
2:fix((3:).minus [5,7..].foldi (\(x:xs)->(x:).union xs) [].map (\p->[p*p, p*p+2*p..]))