Smallest Common Multiple of N numbers

You are given an array numbers. Compute the smallest number multiple with the property that all the number in the array divide it evenly.

Example

Input:

let numbers = [3, 6, 4, 15, 30]

Expected value:

multiple = 60

[collapse]
Hint

Compute the multiple using the primes in the decomposition of the numbers.

Each number can be written using this simple formula:

num = p1<sup>q1</sup> + p2<sup>q2</sup> + p3<sup>q3</sup> + ... + pn<sup>qn</sup>

where p1 is the first prime number, p2 the second and so on. Since our numbers are not very large, we can precompute the first 100 primes. Then decompose the numbers using the primes. The values of power qi is found by dividing each number to the prime pi.

The number obtained by raising all the primes to the largest power qi for every i will be the common multiple of all the initial numbers.

scm = p1<sup>max(q1)</sup> + p2<sup>max(q2)</sup> + p3<sup>max(q3)</sup> + ... + pn<sup>max(qn)</sup>

[collapse]
Solution

let numbers = [3, 6, 4, 15, 30]
func firstNPrimes(N:Int) -> [Int] {

    let maxP = 100
    var isPrime: [Bool] = []
    var primes: [Int] = []
    for _ in 0...maxP {
        isPrime.append(true)
    }
    isPrime[0] = false
    isPrime[1] = false
    for i in 2...maxP {
        if isPrime[i] == true {
            var j = i*i
            while j <= maxP {
                isPrime[j] = false
                j += i
            }
            primes.append(i)
        }
    }

    var solution : [Int] = []
    for i in 0..<N {    
        solution.append(primes[i])
    }
    return solution
}

func raisePower(a:Int, b:Int) -> Int {
    if b == 0 {
        return 1
    }
    else {
        return a * raisePower(a:a,b:b-1)
    }
}

func commonMultiple(nums:[Int]) -> Int {
    let noPrimes = 20
    var primes = firstNPrimes(N:noPrimes)
    var powers = [Int](repeatElement(0, count: noPrimes))

    for i in 0..<numbers.count {
        var element = numbers[i]
        var primeIt = 0
        while element != 1 {
            var newPower = 0
            while element % primes[primeIt] == 0 {
                element /= primes[primeIt]
                newPower += 1
            }
            powers[primeIt] = max(powers[primeIt], newPower)
            primeIt += 1
        }
    }

    var multiple = 1
    for i in 0..<noPrimes {
        multiple *= raisePower(a:primes[i], b:powers[i])
    }
    return multiple
}


var multiple = commonMultiple(nums: numbers)

[collapse]
1 Star2 Stars3 Stars4 Stars5 Stars (8 votes, average: 1.63 out of 5)
Loading...
Subscribe
We send about one email per week with our latest tutorials and updates
Never display this again :)