To generate a list of Fibonacci numbers, we created a generator class that emulates the behavior of the c# yield statement. We’ll expand on this generator in another blog to enable us to write LINQ methods, but for right now we’ll use if for a similar task, generate a list or primes.
Problem 3
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
Writing the Solution First
It seems the easiest way to solve the Euler problems is to write the solution first, then write the functions that support this solution. So here goes.
Dim result = 600851475143.PrimeFactors.Max
What I like about the above code is
· How self explanatory it is.
· The clear path we now have for a solution.
An Extension Method for the Prime Factors of a Long
So let’s build the infrastructure that makes this code actually work. The first thing we’ll need is an extension method to a long that returns all the prime factors for the number.
<Runtime.CompilerServices.Extension()> _
Function PrimeFactors(ByVal n As Long) As IEnumerable(Of Long)
Return New Primes().TakeWhile(Function(p) p <= Math.Sqrt(n)).Where(Function(p) n Mod p = 0)
End Function
Again, I love how declarative of intention this code is. The Linq syntax really makes it easy to follow what the function is doing. Let’s follow along.
· New Primes() generates an as needed list of prime numbers.
· TakeWhile(Function(p) p <= Math.Sqrt(n)) keeps generating our primes until the prime is less than or equal to the square root of the number we’re finding the primes for. The sieve of Eratosthenes lets us know this.
· Where(Function(p) n Mod p = 0) checks if our number can be evenly divided by the prime. If it can then of course it’s a prime factor
A Prime Number Generator
So the only thing we have left to look at is the Primes class that actually generates a list of primes.
Public Class Primes
Inherits Generator(Of Long)
Dim primes As New List(Of Long)
Dim prime = 1
Protected Overrides Function Generate() As Long
Do While prime <= Long.MaxValue
prime += 1
If prime = 2 Then
primes.Add(prime)
Return prime
End If
Dim IsPrime = Function(n) primes.TakeWhile(Function(p) p <= Math.Sqrt(n)).FirstOrDefault(Function(p) n Mod p = 0) = 0
If IsPrime(prime) Then
primes.Add(prime)
Return prime
End If
Loop
End Function
End Class
Because we inherit from Generator, our Return statements behave the same as c# yield statements. Every time we find a prime we add it to the list of primes. The next time the Generate function is called the current number is checked against this list. We really are following the steps from the Sieve of Eratosthenes. Let’s break apart our IsPrime expression.
· Dim IsPrime = Function(n) {expression} = 0 declares a function that takes a long and returns a Boolean. I’ve omitted the expression itself to make it easier to focus on the definition.
· .TakeWhile(Function(p) p <= Math.Sqrt(n)) iterates our current list of primes until the prime is less than or equal to the square root of the number we’re testing.
· FirstOrDefault(Function(p) n Mod p = 0) return the first prime factor or a 0 if there are no prime factors.
· The expression is then checked against 0 to return a Boolean.
A Solution that Now Works
Now that we’ve built the infrastructure, our solution works when run. Go ahead, try it out
Module Module1
Sub Main()
Dim result = 600851475143.PrimeFactors.Max
Console.WriteLine(result)
Console.ReadLine()
End Sub
End Module