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