Prime number lazy sequence

Question

I am new in F# and I am just wondering if is there any way to get lazy sequence of prime numbers in F#.

In Haskell I use next code:

primes :: [Integer]
primes = sieve[2..]
       where sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p > 0]

In F# I can check if is the number is prime:

let isPrime (number : bigint) =
    match number with
        | _ -> seq { bigint(2) .. bigint(Math.Sqrt(float number))}
        |> Seq.exists (fun x -> if (number % x = bigint(0)) then true else false)
        |> not

But I don't know how to convert it to lazy sequence.

Do you need `bigint`? I doubt a sieve is going to be able to compute primes that won't fit in a `long` anytime soon. — Gabe, Mar 23 '11 at 11:44
Yes, I need because I am trying to solve the project eluer #3 task (http://projecteuler.net/index.php?section=problems&id=3). — ceth, Mar 23 '11 at 11:46
small spoiler: the biggest prime factor in that number fits comfortably in a long int. You can also use the I-suffix to denote bigints: 0I instead of bigint 0. — cfern, Mar 23 '11 at 12:50
Sidenote: there is no reason to check for `number % 4` and all the next even numbers - if `number % 2 == 0`, then the check wouldn't happen at all, and if it's not, then one can assume that `number % 4 != 0` as well. — VMAtm, Dec 12 '17 at 20:22

score 8 · Accepted Answer · edited May 23 '17 at 12:25

See this question for a lot of answers giving lazy prime number sequences in F#.

For a naive solution using your isPrime implementation (i.e. I'm thinking you may be interested in seeing how to go about generating a infinite sequence from a filter function in general), try this:

let primes =
    Seq.initInfinite (fun i -> i + 2) //need to skip 0 and 1 for isPrime
    |> Seq.map (fun i -> bigint(i))
    |> Seq.filter isPrime

However, you'll probably want to go about solving Project Euler Problem 3 differently by implementing a function which specifically factorizes a number rather than exhaustively dividing the number by primes and taking the largest. Though you will eventually need a prime sequence generator for problems further on.

score 3 · Answer 2 · edited May 23 '17 at 12:16

If you want to mimic Haskell's laziness, you can use the LazyList type found in FSharp.PowerPack.dll. The LazyList.Cons(p,xs) is a pattern match corresponding to p:xs in Haskell. The 'Delayed' in consDelayed is necessary, because the regular LazyList.cons will be too eager and take infinitely (limited by your patience of course) long.

You might also find this question interesting. It's another Haskell prime sieve in F#.

Here's your code in F# (unfortunately rather ugly):

#r "FSharp.PowerPack.dll"

//A lazy stream of numbers, starting from x
let rec numsFrom x = LazyList.consDelayed x (fun () -> numsFrom (x+1I))

let rec sieve = function
    | LazyList.Cons(p,xs) ->
        LazyList.consDelayed p (fun () -> 
                xs |> LazyList.filter (fun x -> x%p <> 0I) |> sieve)
    | _ -> failwith "This can't happen with infinite lists"

let primes() = sieve (numsFrom 2I)

Example output in FSI:

> primes() |> Seq.take 14 |> Seq.toList;;
Real: 00:00:00.000, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val it : System.Numerics.BigInteger list =
  [2I; 3I; 5I; 7I; 11I; 13I; 17I; 19I; 23I; 29I; 31I; 37I; 41I; 43I]

score 1 · Answer 3 · answered Sep 01 '11 at 07:17

My solution without F# powerpack

module Prime
    let isPrime n = 
        let bound = int (sqrt(float n))
        seq{2..bound}
        |> Seq.exists (fun x -> n % x = 0) 
        |> not
    let rec nextPrime n = 
        if isPrime (n + 1) then n + 1
        else nextPrime (n+1)
    let sequence = 
        Seq.unfold(fun n -> Some(n, nextPrime n)) 1

Prime number lazy sequence

3 Answers3