## 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

Labels:
Algorithms

Subscribe to:
Posts (Atom)