Saturday, October 15, 2011
Friday, September 30, 2011
Common multiple
Q: Given two numbers m and n, write a method to return the first number r that is
divisible by both (e.g., the least common multiple).
A:
The Approach:
What does it mean for r to be divisible by m and n? It means that all the primes in m must go into r, and all primes in n must be in r. What if m and n have primes in common?
For example, if m is divisible by 3^5 and n is divisible by 3^7, what does this mean about r? It means r must be divisible by 3^7.
The Rule: For each prime p such that p^a \ m (e.g., m is divisible by p^a) and p^b \ n, r must be divisible by p^max(a, b)
The Algorithm:
Define q to be 1.
for each prime number p less than m and n:
find the largest a and b such that p^a \ m and p^b \ n
let q = q * p^max(a, b)
return q
divisible by both (e.g., the least common multiple).
A:
The Approach:
What does it mean for r to be divisible by m and n? It means that all the primes in m must go into r, and all primes in n must be in r. What if m and n have primes in common?
For example, if m is divisible by 3^5 and n is divisible by 3^7, what does this mean about r? It means r must be divisible by 3^7.
The Rule: For each prime p such that p^a \ m (e.g., m is divisible by p^a) and p^b \ n, r must be divisible by p^max(a, b)
The Algorithm:
Define q to be 1.
for each prime number p less than m and n:
find the largest a and b such that p^a \ m and p^b \ n
let q = q * p^max(a, b)
return q
Subscribe to:
Posts (Atom)