Many of the Project Euler problems require prime number to solve, so I wrote a prime number generator in both F# and C#.  I think that my implementation in C# is more efficient since I have not figured out how to do a takewhile with a list in F#.

F# prime numbers 

let primes = 

  let rec prim n (sofar: list<int64>) = 

      seq { if (sofar |> List.for_all (fun i -> n % i <> 0L)) then 

                yield n

                yield! prim (n+1L) (n :: sofar) 

            else 

                yield! prim (n+1L) sofar }

  prim 2L []

C# prime number class 

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

 

namespace PrimeNumbers

{

    public class Primes : IEnumerable<long>

    {

        #region IEnumerable<long> Members

 

        public IEnumerator<long> GetEnumerator()

        {

            yield return 2;

            var primesSoFar = new List<long>();

            primesSoFar.Add(2);

 

            Func<long, bool> IsPrime = n => primesSoFar.TakeWhile(p => p <= (long)Math.Sqrt(n)).FirstOrDefault(p => n % p == 0) == 0;

            for (int i = 3; true; i += 2)

            {

                if (IsPrime(i))

                {

                    yield return i;

                    primesSoFar.Add(i);

                }

            }

        }

 

        #endregion

 

        #region IEnumerable Members

 

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()

        {

            return GetEnumerator();

        }

 

        #endregion

    }

}

Problem #3:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

 

F# 

module Seq =

  let takeWhile f (ie : #seq<'a>) =

    seq { use e = ie.GetEnumerator()

          while e.MoveNext() && f e.Current do

            yield e.Current }

 

let primes = 

  let rec prim n (sofar: list<int64>) = 

      seq { if (sofar |> List.for_all (fun i -> n % i <> 0L)) then 

                yield n

                yield! prim (n+1L) (n :: sofar) 

            else 

                yield! prim (n+1L) sofar }

  prim 2L []

 

 

let largestfactor n = primes |> 

                      Seq.takeWhile(fun x -> x < int64 (System.Math.Sqrt(float n))) |> 

                      Seq.filter (fun x ->  n % x = 0L) |> 

                      Seq.fold (fun a x -> if x > a then x else a ) 0L

 

let lastprime = largestfactor 600851475143L 

 

printf "%i" lastprime

C# 

const long n = 600851475143;

var t = new Primes().TakeWhile(x => x < (long) Math.Sqrt(n)).Where(x => n % x == 0).Last();

Problem #7:

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10001st prime number?

F# 

let primes = 

  let rec prim n (sofar: list<int64>) = 

      seq { if (sofar |> List.for_all (fun i -> n % i <> 0L)) then 

                yield n

                yield! prim (n+1L) (n :: sofar) 

            else 

                yield! prim (n+1L) sofar }

  prim 2L []

  

let primes10001 = Seq.take 10001 primes

 

let toLargest l = List.fold1_left max l

let lastprime = primes10001 |> toLargest

 

printf "%i" lastprime

C# 

var p = new Primes().Take(10001).Last();

Note: All of the C# code samples are using  the prime numbers class.

del.icio.us Tags: ,,