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

Related Posts on Geeks With Blogs
Matching Categories

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.

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 :)

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>

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

I don't fully understand what you mean by this, which function are you referring to - the primenumbersOf?

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

http://stackoverflow.com/questions/2053691/can-the-execution-time-of-this-prime-number-generator-be-improved

<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>

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]