# 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]
(5 votes, average: 1.80 out of 5)