# Project Euler #3 (Largest prime factor) in Swift

Posted on

Problem

As mentioned in Project Euler #2 in Swift, I intend to work my way through Project Euler using Swift to make sure there aren’t any tricks I’m missing.

This is the problem statement for #3:

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

What is the largest prime factor of the number 600851475143?

This solution if fewer lines of code, but it is recursive (and I don’t know about you, but recursion usually takes me a second to wrap my head around).

Here’s my solution:

``````import Darwin

extension Int {
func isMultipleOf(factor: Int) -> Bool {
return self % factor  == 0
}
func largestPossibleFactor() -> Int {
let squareRoot: Double = sqrt(Double(self))
return Int(ceil(squareRoot))
}
}

func findLargestPrimeFactor(let fromNumber: Int) -> Int {
for factor in 2..<fromNumber.largestPossibleFactor() {
if fromNumber.isMultipleOf(factor) {
return findLargestPrimeFactor(fromNumber/factor)
}
}
return fromNumber
}

let target: Int = 600_851_475_143

``````

I like Flambino’s tip of using extensions and can’t believe I forgot about it in my last question (which is part of why I’m doing this–build muscle memory), but I did manage to implement it here.

In plain-English, here’s how the `findLargestPrimeFactor` algorithm works.

Starting at two, we start checking numbers to see whether or not it’s a factor of the starting `fromNumber`. If we find one, then `fromNumber` obviously isn’t prime, so we return the largest possible prime of `fromNumber` divided by `possibleFactor` (which we now know is an actual factor).

We’re essentially just dividing the `fromNumber` by its factors until we get to a number that has no factors (and is therefore prime).

Solution

## Naming

• `fromNumber` is a bad name for that variable. Something like `toFactor` would be better.
• `largestPossibleFactor` is very broken. The function does not return the largestPossibleFactor, it instead returns an approximate square value. Take the number `36`, the largest possible factor (other than 36 itself), is 18, yet your function returns 6. What you should call the function is something like …. actually, I don’t think it needs to be a function at all…. it’s over-extracted, calling a 1-liner function who’s code is easier to write than describe. It’s buggy code, anyway….

## Bug

Your range limit is the ‘half-open’ range limit: `2..<Int(ceil(squareRoot))`

The intention of this code is to identify where to stop the factor checking. This code will fail for values like … 9. For 9 your code will not factor it at all, because it is a square of a prime, so your squareRoot will calculate the valeu `3`, and you will do the ceil of that (3), and then exclude `3` in the range, so you will not factor the value 9 at all, and call it prime.

Instead, you should simply use the full range operator, and truncate the square-root:

``````for i in 2...Int(squareRoot)
``````

## Performance

A small optimization is possible if you are interested, by limiting the start of the range of the factor tests. Consider converting the recursive part of your function to include the start of the range as well as the number to factor. Something like:

``````func findLargestPrimeFactorFrom(let smallest: Int, let toFactor: Int) -> Int {
for factor in smallest...Int(sqrt(Double(toFactor))) {
if toFactor.isMultipleOf(factor) {
return findLargestPrimeFactor(factor, toFactor/factor)
}
}