You are given an array numbers. Compute the smallest number multiple with the property that all the number in the array divide it evenly.
Input:
let numbers = [3, 6, 4, 15, 30]Expected value:
multiple = 60
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>
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)
