7
\$\begingroup\$

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

let answer: Int = findLargestPrimeFactor(target)

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

\$\endgroup\$
6
\$\begingroup\$

Naming

Your naming is misleading, and effectively broken:

  • 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)
        }
    }
    return toFactor
}

The reason it will be faster is because in your recursion, you will never need to check values smaller than factors you have already eliminated higher up the stack.

\$\endgroup\$
  • \$\begingroup\$ I think I'd make smallest an optional argument that defaults to 2, yes? \$\endgroup\$ – nhgrif Aug 24 '14 at 11:44
  • \$\begingroup\$ @nhgrif - yes, that would work well. \$\endgroup\$ – rolfl Aug 24 '14 at 11:55
5
\$\begingroup\$

I'd like to offer a quick optimization on the factoring loop:

2 is the only even factor that needs to be tested, as any other larger even number will be a multiple of 2, so will never be tested, because the loop will terminate at 2. You can then have a special case for 2 and then iterate only by the odd values to cut the search space by nearly half.

If you want even more performance, I would suggest looking into a well known fast factorization method such as the Quadratic sieve.

Update: added rofl's clarification of my previous statement

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.