Helpful Algorithms

Greatest Common Divisor

func gcd(_ first: Int, _ second: Int) -> Int {
    var x: Int = first
    var y: Int = second
    while y > 0 {
        (x, y) = (y, x % y)
    }
    return x
}

Lowest Common Multiple

func lcm(_ first: Int, _ second: Int) -> Int {
    if first == 0 && second == 0 { return 0 }
    var x: Int = first
    var y: Int = second
    while y > 0 {
        (x, y) = (y, x % y)
    }
    return (first * second) / x
}

func lcm(_ numbers: [Int]) -> Int {
    if numbers.count < 2 { return 0 }
    var baseNumber: Int = numbers.first!
    for index in 1 ..< numbers.endIndex {
        baseNumber = lcm(baseNumber, numbers[index])
    }
    return baseNumber
}

Palindrome Check

import Foundation

extension String {
    var isPalindrome: Bool {
        let s: String = String(self.unicodeScalars.filter({CharacterSet.alphanumerics.contains($0)})).lowercased()
        return s == String(s.reversed())
    }
}

Primality Check

Note: This algorithm uses a languages standard square root function. Most languages have efficient implementations of the function that are faster than anything else that could be coded by hand.

extension Int {
    var isPrime: Bool {
        if self <= 1 { return false }
        if self % 2 == 0 { return self == 2 }
        if self % 3 == 0 { return self == 3 }
        let r: Int = Int(Double(self).squareRoot())
        var f: Int = 5
        while f <= r {
            if self % f == 0 || self % (f + 2) == 0 { return false }
            f += 6
        }
        return true
    }
}

Prime Factors

extension Int {
    var primeFactors: [Int] {
        var f: [Int] = []
        var i: Int = 2
        var m: Int = self
        while i <= m {
            if m % i == 0 {
                f.append(i)
                m /= i
            } else { i += 1 }
        }
        return f
    }
}

Prime Numbers Using the Sieve of Eratosthenes

The sieve of Eratosthenes returns all prime numbers up to the value n provided to the function. This implementation returns the values as an array.

Note: For large enough values of n, some environments might run out of memory due to the initial large boolean array. If this is the case, running all numbers against the above mentioned primality check is faster than modifying this algorithm to check against known primes.

func primeSieve(_ target: Int) -> [Int] {
    if target <= 1 { return [] }
    if target == 2 { return [2] }
    if target == 3 { return [2, 3] }
    let targetSquareRoot = Int(Double(target).squareRoot())
    var checks: [Bool] = Array(repeating: true, count: target + 1)
    var primes: [Int] = []
    for number in 2...targetSquareRoot {
        if checks[number] {
            primes.append(number)
            for notPrime in stride(from: number * number, to: target + 1, by: number) { checks[notPrime] = false }
        }
    }
    for number in (targetSquareRoot + 1)...target {
        if checks[number] { primes.append(number) }
    }
    return primes
}