Geeks With Blogs
Mark Pearl

 

So this weekend I made an attempt at problem 3 of Project Euler.

Problem 3

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

What is the largest prime factor of the number 600851475143 ?

My Solution

 

//
// Checks whether a number is prime or not using the Trial Division approach
// To improve performance I have only pass through odd numbers greater than 2 and do not check for this case
//
let isPrime (number : bigint) =
    match number with        
        | _ -> seq { bigint(2) .. bigint(1) .. bigint (Math.Sqrt (float number))}    
                |> Seq.exists (fun x -> if (number % x = bigint(0)) then true else false)      
                |> not        


//
// Returns a sequence of prime numbers up to number x
//
let primenumbersOf (number : bigint) =    
    let oddPrimes = seq { bigint(3).. bigint(2) .. number} |> Seq.filter(fun x -> isPrime x)                
    Seq.append [bigint(2)] oddPrimes


//
// Returns a sequence of prime factors of a specific number x
//
let primefactornumbersOf (number : bigint) =
    primenumbersOf (number / bigint(Math.Sqrt(float(number))))    
    |> Seq.filter(fun x -> number % x = bigint(0))
    

primefactornumbersOf(bigint(600851475143.0)) |> Seq.iter (fun x -> Console.WriteLine(x))
Console.WriteLine("Finished")
Console.ReadLine()

It works fine except it is not the most performant approach. I would appreciate any feedback from people that could maybe help me look at a different approach that would return a quicker result.

Posted on Monday, June 21, 2010 8:07 AM F# | Back to top


Comments on this post: F# Project Euler Problem 3

# re: F# Project Euler Problem 3
Requesting Gravatar...
Hi,

the most obvious improvement is to begin with (number - 1) and count down to the square-root of this number and only looking for the first result from this sequence.
If there isn't anything special about the given number (didn't check and didn't think it through) that might be the only improvement you can get.

Greetings
Left by Carsten on Jun 21, 2010 2:16 PM

# re: F# Project Euler Problem 3
Requesting Gravatar...
Thanks Carsten...

I don't fully understand what you mean by this, which function are you referring to - the primenumbersOf?
Left by Mark Pearl on Jun 21, 2010 6:28 PM

# re: F# Project Euler Problem 3
Requesting Gravatar...
Your solution is surely the easiest to understand :)

In isPrime, you could check for divisibility by 2, and then only by odd numbers.

Somethings I have done before are:

1) Sieve of Eratosthenes to find the prime numbers up to sqrt(N). With numbers this big, I end up doing it in stages... the primes up to 1000, then use them to find the primes up to 1 million, then use them to find the primes to sqrt(N). Even in python, this worked ok for this problem, but is not purely functional, if that is what you are going for.

2) I have just recently played with the Miller-Rabin primality test. It is probabilistic, but on the Wikipedia page there are citations that give a fixed set of numbers to try that will definitely work for any n < some limit. It looks like it should be much faster than option #1, but it is a lot more code. More fun, too, if you like the math. Since you are doing Euler problems, you probably like the math :)

Have fun, and I hope that makes sense.

Dave
Left by dave on Jun 24, 2010 4:06 PM

# re: F# Project Euler Problem 3
Requesting Gravatar...
See here for a very fast way to generate/test prime numbers in F#:

http://stackoverflow.com/questions/2053691/can-the-execution-time-of-this-prime-number-generator-be-improved
Left by Joel on Jun 24, 2010 6:10 PM

# re: F# Project Euler Problem 3
Requesting Gravatar...
I had a stab at this on my blog rebrained.com. Using Numpy, this is what I got:

<pre>
import math
import numpy
def prime6(upto):
primes=numpy.arange(3,upto+1,2)
isprime=numpy.ones((upto-1)/2,dtype=bool)
for factor in primes[:int(math.sqrt(upto))]:
if isprime[(factor-2)/2]: isprime[(factor*3-2)/2:(upto-1)/2:factor]=0
return numpy.insert(primes[isprime],0,2)
</pre>
Left by nolfonzo on Sep 03, 2010 9:46 PM

# re: F# Project Euler Problem 3
Requesting Gravatar...
Thanks Nolfonzo - I must admit, up to today I had never heard of Numpy... nice to see something new!
Left by MarkPearl on Sep 04, 2010 7:34 AM

# re: F# Project Euler Problem 3
Requesting Gravatar...

Try this only took 2 second to run



let rec ifPrimeNumber biggestnumber smallernumber =

match biggestnumber with

| 1L -> 1L :: []
| _ ->
let x = biggestnumber % smallernumber
match x with
| 0L ->
let newB = biggestnumber / smallernumber
match newB with
| 1L -> smallernumber :: []
| _ -> smallernumber :: ifPrimeNumber newB ( smallernumber + 1L )

| _ -> ifPrimeNumber biggestnumber ( smallernumber + 1L )



> let y = ifPrimeNumber 600851475143L 1L ;;
Real: 00:00:00.000, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0

val y : int64 list = [1L; 71L; 839L; 1471L; 6857L]

Left by khan on Dec 22, 2010 4:12 PM

Your comment:
 (will show your gravatar)


Copyright © MarkPearl | Powered by: GeeksWithBlogs.net